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<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;


vector<P> G[100001];
vector<P> dp1(100000);
P dfs1(int u,int t){
    P ret;
    ret.first=0;
    ret.second=0;
    for(auto v:G[u]){
        if(v.first==t) continue;
        P p = dfs1(v.first,u);
        ret.first=max(ret.first,p.first+v.second);
        ret.second=max({ret.second,p.second,v.second});
    }
    return dp1[u]=ret;
}

int dfs2(int u,int t,int d,int e){
    vector<pair<P,int>> A;
    vector<P> dd,ee;
    A.push_back({{0,0},-1});
    A.push_back({{0,0},-1});
    for(auto v:G[u]){
        if(v.first==t){
            A.push_back({{d+v.second,e},v.first});
        }
        else{
            A.push_back({{dp1[v.first].first+v.second,max(dp1[v.first].second,v.second)},v.first});
        }
    }
    sort(A.rbegin(),A.rend());
    int ret=0;
    for(auto v:A){
        int sum = v.first.second;
        if(v.second==A[0].second){
            sum += A[1].first.first;
            sum += A[2].first.first;
        }
        else if(v.second==A[1].second){
            sum += A[0].first.first;
            sum += A[2].first.first;
        }
        else{
            sum += A[0].first.first;
            sum += A[1].first.first;
        }
        ret = max(ret,sum);

        dd.push_back({v.first.first,v.second});
        ee.push_back({v.first.second,v.second});
    }
    sort(dd.rbegin(),dd.rend());
    sort(ee.rbegin(),ee.rend());
    for(auto v:G[u]){
        if(v.first==t) continue;
        int nd=dd[0].first,ne=ee[0].first;
        if(dd[0].second==v.first) nd=dd[1].first;
        if(ee[0].second==v.first) ne=ee[1].first;
        ret=max(ret,dfs2(v.first,u,nd,max(ne,v.second)));
    }
    return ret;
}

int main(){
    int n;cin >> n;
    for (int i = 0; i < n-1; i++) {
        int p,w;cin >> p >> w;
        G[i+1].push_back({p,w});
        G[p].push_back({i+1,w});
    }
    dfs1(0,-1);
    cout << dfs2(0,-1,0,0) << endl;
}

