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 vector<int> vi;
typedef vector<ll> vl;
typedef complex<double> P;
typedef pair<int,int> pii;
#define REP(i,n) for(ll i=0;i<n;++i)
#define REPR(i,n) for(ll i=1;i<n;++i)
#define FOR(i,a,b) for(ll i=a;i<b;++i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define MOD (ll)(1e9+7)
#define ADD(a,b) a=((a)+(b))%MOD
#define FIX(a) ((a)%MOD+MOD)%MOD

struct edge{
  int to,cost,id;
  edge(){}
  edge(int to,int cost,int id):to(to),cost(cost),id(id){}
};

int n;
vector<edge> g[125252];
int weight[125252];
bool used[125252];
queue<int> Q;

int dist[125252];
int calc(int s, int ban){
  int a=s, mxd=0;
  REP(i,n)dist[i]=-1;
  dist[s] = 0;
  Q.push(s);
  while(!Q.empty()){
    int p = Q.front();Q.pop();
    REP(i,g[p].size()){
      edge e = g[p][i];
      if(e.id == ban)continue;
      int to = e.to;
      if(dist[to]>=0)continue;
      dist[to] = dist[p] + e.cost;
      if(dist[to] > mxd){
        mxd = dist[to];
        a = to;
      }
      Q.push(to);
    }
  }
  REP(i,n)dist[i]=-1;
  dist[a] = 0;
  int r = a;
  Q.push(a);
  while(!Q.empty()){
    int p = Q.front();Q.pop();
    REP(i,g[p].size()){
      edge e = g[p][i];
      if(e.id == ban)continue;
      int to = e.to;
      if(dist[to]>=0)continue;
      dist[to] = dist[p] + e.cost;
      if(dist[to]>dist[r])r=to;
      Q.push(to);
    }
  }
  return r;
}

int calc2(int end){
  REP(i,n-1)used[i]=false;
  int cur = end;
  while(dist[cur]>0){
    REP(i,g[cur].size()){
      edge e = g[cur][i];
      if(dist[e.to]<dist[cur]){
        cur = e.to;
        used[e.id] = true;
        break;
      }
    }
  }
  int ret = 0;
  REP(i,n-1)if(!used[i]) ret = max(ret,weight[i]);
  return ret;
}

int main(){
  scanf("%d",&n);
  int mxweight = 0;
  int src = 0,dst = 0,id = 0;
  REP(i,n-1){
    int to,w;
    scanf("%d%d",&to,&w);
    int from = i+1;
    g[from].push_back(edge(to,w,i));
    g[to].push_back(edge(from,w,i));
    if(w>mxweight){
      mxweight = w;
      src = from;
      dst = to;
      id = i;
    }
    weight[i] = w;
  }
  int ans = 0;
  // ??´???
  int end = calc(0,-1);
  int mxw = calc2(end);
  ans = max(ans,dist[end]+mxw);
  // ??¶??£?????????
  int cand = dist[calc(src,id)];
  cand = max(cand, dist[calc(dst,id)]);
  ans = max(ans,cand+mxweight);
  printf("%d\n",ans);
  return 0;
}