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 long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF 1e16
#define mod 1000000007

int N;
vector<P> g[100010];
int dist[2][100010];
int s,t;
int mxl[100010],mxr[100010];
multiset<int> mxlst,mxrst;
vector<int> vs;
int dia,res;

void dfs(int v,int pre,int dep,int i){
  dist[i][v]=dep;
  for(P p : g[v]){
    if(p.fi==pre)continue;
    dfs(p.fi,v,dep+p.se,i);
  }
}

void dfs2(int v,int pre,int i){
  maxch(mxl[i],dist[0][v]);
  maxch(mxr[i],dist[1][v]);
  for(P p : g[v]){
    if(p.fi==pre){
      maxch(res,p.se+dia);
      continue;
    }
    dfs2(p.fi,v,i);
  }
}

int main(){
  cin>>N;
  rep(i,N-1){
    int p,w;
    cin>>p>>w;
    g[i+1].push_back(P(p,w));
    g[p].push_back(P(i+1,w));
  }
  dfs(0,-1,0,0);
  s=0;
  rep(i,N)if(dist[0][i]>dist[0][s])s=i;
  dfs(s,-1,0,0);
  t=0;
  rep(i,N)if(dist[0][i]>dist[0][t])t=i;
  dfs(t,-1,0,1);

  while(t!=s){
    for(P p : g[t]){
      if(dist[0][p.fi]<dist[0][t]){
        dia+=p.se;
        vs.push_back(t);
        t=p.fi;
      }
    }
  }
  vs.push_back(s);
  reverse(all(vs));
  int M=vs.size();

  rep(i,M){
    int v=vs[i];
    mxl[i]=dist[0][v];
    mxr[i]=dist[1][v];
    for(P p : g[v]){
      if(i>0&&vs[i-1]==p.fi)continue;
      if(i<M-1&&vs[i+1]==p.fi)continue;
      dfs2(p.fi,v,i);
    }
    mxrst.insert(mxr[i]);
  }

  rep(i,M-1){
    int u=vs[i],v=vs[i+1];
    mxlst.insert(mxl[i]);
    mxrst.erase(mxrst.find(mxr[i]));
    for(P p : g[u]){
      if(p.fi==v){
        if(mxrst.size())maxch(res,p.se+*mxrst.rbegin());
        if(mxlst.size())maxch(res,p.se+*mxlst.rbegin());
      }
    }
  }
  
  cout<<res<<endl;

  return 0;
}

