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 uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
template<class T = ll> constexpr T TEN(int n) {return (n==0)?1:10*TEN<T>(n-1);}

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

template<class E, class N>
struct AllTree {
    vector<N> sm;
    vector<vector<N>> ldp, rdp;
    AllTree(const Graph<E> &g) {
        int n = (int)g.size();
        sm = vector<N>(n);
        ldp = vector<vector<N>>(n);
        rdp = vector<vector<N>>(n);
        for (int i = 0; i < n; i++) {
            int dg = (int)g[i].size();
            ldp[i].resize(dg+1);
            rdp[i].resize(dg+1);
        }
        first(g, 0, -1);
        dfs(g, 0, -1, N());
    }
    void first(const Graph<E> &g, int p, int b) {
        sm[p] = N();
        for (const E &e: g[p]) {
            int d = e.to;
            if (d == b) continue;
            first(g, d, p);
            N n = sm[d]; n.first(e);
            sm[p] = sm[p] + n;
        }
        sm[p].finish(p);
    }
    void dfs(const Graph<E> &g, int p, int b, N r) {
        int dg = (int)g[p].size();
        vector<N> &ln = ldp[p], &rn = rdp[p];
        ln[0] = N();
        for (int i = 0; i < dg; i++) {
            int d = g[p][i].to;
            N n;
            if (d == b) {
                n = r;
            } else {
                n = sm[d];
            }
            n.first(g[p][i]);
            ln[i+1] = ln[i] + n;
        }
        rn[dg] = N();
        for (int i = dg-1; i >= 0; i--) {
            int d = g[p][i].to;
            N n;
            if (d == b) {
                n = r;
            } else {
                n = sm[d];
            }
            n.first(g[p][i]);
            rn[i] = rn[i+1] + n;
        }
        for (int i = 0; i < dg; i++) {
            int d = g[p][i].to;
            if (d == b) continue;
            N n = ln[i]+rn[i+1]; n.finish(p);
            dfs(g, d, p, n);
        }
    }
    N get(int p, int idx = -1) {
        N n;
        if (idx == -1) {
            n = ldp[p].back();
        } else {
            n = ldp[p][idx]+rdp[p][idx+1];
        }
        n.finish(p);
        return n;
    }
};

struct Node {
    // first??? ???????????¨->?£?
    // finish????£?->???????????¨
    int rad, dia;
    int rd[2];
    Node() {
        // !!!!!?£?????????????????????¨!!!!!
        rad = -1; dia = 0;
        rd[0] = rd[1] = 0;
    }
    template<class E>
    void first(const E &e) {
        // ???????????¨->?£? ????????????????????????????????????
        rd[0] = rad+e.dist;
        rd[1] = 0;
    }
    const 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];
        assert(n.rd[0] == max(rd[0], r.rd[0]));
        n.dia = max(dia, r.dia);
        return n;
    }
    void finish(int idx) {
        // ???????????¨??????idx???????????????????????????
        rad = rd[0];
        dia = max(dia, rd[0]+rd[1]);
    }
};

struct Edge { int to, dist; };

int main2() {
    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<Edge, Node> dp(g);
    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;
}

/**
 * stack size??????????????? 64bit??¨
 */
int main() {
    static ll eord, enew;
    const int sz = 256*1024*1024;
    static unsigned char *p = (unsigned char*)malloc(sz);
    enew = ((ll)(p+sz-1) & ~0xff);
    __asm__ volatile("mov %%rsp, %0" : "=r"(eord));
    __asm__ volatile("mov %0, %%rsp" : : "r"(enew));
    main2();
    __asm__ volatile("mov %0, %%rsp" : : "r"(eord));
    return 0;
}