Problem statement

There is a village called Biwako, which consists of $ N $ islets floating on the lake. Biwako Village has a simple bridge with $ N-1 $ books. The islands are numbered from $ 0 $ to $ N-1 $, and the bridges are numbered from $ 0 $ to $ N-2 $. The $ i $ bridge directly connects the $ i + 1 $ island and the $ p_i $ island, and is $ w_i $ in length. Villagers can move between islands through several bridges.

At the suggestion of a villager, a relay tournament will be held in Biwako Village. However, since there is no closed road in Biwako Village and trucks cannot be prepared, I decided to make a closed road by replacing the existing bridge by only $ 1 $. Find the length of the cycle that can be prepared by this operation and that has the maximum length.

Constraint

$ 2 \ leq N \ leq 100000 $
$ 0 \ leq p_i \ leq N-1 $
$ 1 \ leq w_i \ leq 1000 $
All integers
Reachable between all islands

sample

The illustration of each sample is as follows.

<image>

Sample input 1


Five
0 1
0 2
0 3
0 4


Sample output 1


9


Sample input 2


12
0 6
1 1
0 3
3 4
0 2
5 1
6 1
0 2
8 1
9 1
10 2


Sample output 2


19


Sample input 3


2
0 1


Sample output 3


1




input

$ N $
$ p_0 \ w_0 $
$ \ vdots $
$ p_ {n-2} \ w_ {n-2} $

output

Print the answer on the $ 1 $ line.

Example

Input

5
0 1
0 2
0 3
0 4


Output

9
#include <iostream>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <vector>
#include <valarray>
#include <array>
#include <queue>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <complex>
#include <random>

using namespace std;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) {return (n==0)?1:10*TEN(n-1);}

template <class E>
using Graph = vector<vector<E>>;

struct TreeOrd {
    using P = pair<int, int>;
    vector<P> s, rs;
    template<class E>
    TreeOrd(const Graph<E> &g, int r = 0) {
        s.push_back(P(r, -1));
        for (int i = 0; i < int(s.size()); i++) {
            P p = s[i];
            for (E e: g[p.first]) {
                if (e.to == p.second) continue;
                s.push_back(P(e.to, p.first));
            }            
        }
        rs = vector<P>(s.rbegin(), s.rend());
    }
};

template<class N>
struct AllTree {
    vector<vector<N>> ldp;
    AllTree() {}
    template<class E>
    AllTree(const Graph<E> &g, const TreeOrd &t, int r = 0) {
        int n = (int)g.size();
        auto sm = vector<N>(n), top = vector<N>(n);
        ldp = vector<vector<N>>(n);
        for (int i = 0; i < n; i++) {
            ldp[i].resize(int(g[i].size())+1);
        }
        for (auto pa: t.rs) {
            // first
            int p, b; tie(p, b) = pa;
            sm[p] = N();
            for (const E &e: g[p]) {
                int d = e.to;
                if (d == b) continue;
                sm[p] = sm[p] + N(sm[d]).first(p, e);
            }
            sm[p].finish(p);
        }
        top[r] = N();
        for (auto pa: t.s) {
            // second
            int p, b; tie(p, b) = pa;
            int dg = (int)g[p].size();
            vector<N> &ln = ldp[p];
            ln[0] = N();
            for (int i = 0; i < dg; i++) {
                int d = g[p][i].to;
                ln[i+1] = ln[i] + N(d==b ? top[p] : sm[d]).first(p, g[p][i]);
            }
            N rnode = N();
            for (int i = dg-1; i >= 0; i--) {
                int d = g[p][i].to;
                if (d != b) {
                    top[d] = (ln[i]+rnode).finish(p);
                }
                ln[i] = ln[i] + rnode;
                rnode = rnode + N(d==b ? top[p] : sm[d]).first(p, g[p][i]);
            }
        }
    }
    N get(int p, int idx = -1) {
        if (idx == -1) idx = int(ldp[p].size())-1;
        return N(ldp[p][idx]).finish(p);
    }
};

struct Node {
    // first??? ???????????¨->?£?
    // finish????£?->???????????¨
    int rad, dia;
    int rd[2];
    Node() {
        // !!!!!?£?????????????????????¨!!!!!
        rad = 0; dia = 0;
        rd[0] = rd[1] = 0;
    }
    template<class E>
    Node first(int par, const E &e) {
        // ???????????¨->?£? ????????????????????????????????????
        rd[0] = rad+e.dist;
        rd[1] = 0;
        return *this;
    }
    Node operator+(const Node &r) {
        // ?????????????????? ?????????????????????????????¨????????¨??????????????????
        Node n;
        vector<int> v;
        v.push_back(rd[0]); v.push_back(rd[1]);
        v.push_back(r.rd[0]); v.push_back(r.rd[1]);
        sort(begin(v), end(v), greater<int>());
        n.rd[0] = v[0];
        n.rd[1] = v[1];
        n.dia = max(dia, r.dia);
        return n;
    }
    Node finish(int par) {
        // ???????????¨??????idx???????????????????????????
        rad = rd[0];
        dia = max(dia, rd[0]+rd[1]);
        return *this;
    }
};

struct Edge { int to, dist; };

int main() {
    ios::sync_with_stdio(0);
    int n;
    cin >> n;
    Graph<Edge> g(n);
    for (int i = 1; i < n; i++) {
        int j, d;
        cin >> j >> d;
        g[i].push_back(Edge{j, d});
        g[j].push_back(Edge{i, d});
    }
    AllTree<Node> dp(g, TreeOrd(g, 0));
    int ans = -1;
    for (int p = 0; p < n; p++) {
        int dg = (int)g[p].size();
        for (int i = 0; i < dg; i++) {
            Edge &e = g[p][i];
            ans = max(ans, e.dist + dp.get(p, i).dia);
        }
    }
    cout << ans << endl;
    return 0;
}