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 int TEN(int n) {return (n==0)?1:10*TEN(n-1);}

using P = pair<int, ll>;
using L = array<ll, 3>;

const int MN = 100100;

int n;
int rt[MN];
ll rw[MN];
vector<P> g[MN];

L mer(L a, L b) {
    L r;
    r[0] = 0;
    r[1] = max(a[1], b[1]);
    r[2] = max(max(a[2], b[2]), a[1]+b[1]);
    r[2] = max(r[2], r[1]);
    r[1] = max(r[1], r[0]);
    return r;
}

array<ll, 3> md[MN], pmd[MN];

void dfs(int p, int b) {
    rt[p] = b;
    vector<ll> v;
    md[p][0] = md[p][1] = md[p][2] = 0;
    for (P ed: g[p]) {
        int q; ll w;
        tie(q, w) = ed;
        if (q == b) continue;
        rw[q] = w;
        dfs(q, p);
        L ri = md[q];
        ri[1] += w;
        ri[2] = max(ri[2], ri[1]);
        md[p] = mer(md[p], ri);
    }
}

void dfs2(int p, int b) {
    int m = (int)g[p].size();
    vector<L> lmd(m+1), rmd(m+1);
    lmd[0].fill(0);
    for (int i = 0; i < m; i++) {
        int q; ll w;
        tie(q, w) = g[p][i];
        lmd[i+1] = lmd[i];
        if (q == b) continue;
        L ri = md[q];
        ri[1] += w;
        ri[2] = max(ri[2], ri[1]);
        lmd[i+1] = mer(lmd[i+1], ri);
    }

    rmd[m].fill(0);
    for (int i = m-1; i >= 0; i--) {
        int q; ll w;
        tie(q, w) = g[p][i];
        rmd[i] = rmd[i+1];
        if (q == b) continue;
        L le = md[q];
        le[1] += w;
        le[2] = max(le[2], le[1]);

        rmd[i] = mer(rmd[i], le);
    }

    for (int i = 0; i < m; i++) {
        int q; ll w;
        tie(q, w) = g[p][i];
        if (q == b) continue;
        L buf = mer(lmd[i], rmd[i+1]);
        if (b != -1) {
            L pa = pmd[p];
            pa[1] += rw[p];
            pa[2] = max(pa[2], pa[1]);
            buf = mer(pa, buf);
        }
        pmd[q] = buf;
    }

    for (int i = 0; i < m; i++) {
        int q; ll w;
        tie(q, w) = g[p][i];
        if (q == b) continue;
        dfs2(q, p);
    }
}

void main2() {
    cin >> n;
    static int p2[MN];
    static ll W[MN];
    for (int i = 1; i <= n-1; i++) {
        int p, w;
        cin >> p >> w;
        p2[i] = p; W[i] = w;
        g[i].push_back(P(p, w));
        g[p].push_back(P(i, w));
    }
    dfs(0, -1);
/*    for (int i = 0; i < n; i++) {
        printf("%lld %lld %lld\n", md[i][0], md[i][1], md[i][2]);
    }*/
    pmd[0].fill(0);
//    printf("\n");
    dfs2(0, -1);
/*    for (int i = 0; i < n; i++) {
        printf("%lld %lld %lld\n", pmd[i][0], pmd[i][1], pmd[i][2]);
    }*/
    ll ans = 0;
    for (int i = 1; i <= n-1; i++) {
        int a = i, b = p2[i];
        if (rt[b] == a) swap(a, b);
        //rt[a] == b
        ans = max(ans, md[a][2]+W[i]);
        ans = max(ans, pmd[a][2]+W[i]);
    }
    cout << ans << endl;
}

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;
}