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
/*

??¨????????¨DP.
Node????????????????????????
BidirectionalTreeDP<Node> treedp(G);
??¨????????°??????
get(v)??§v????????¨??????dp??????get(v,p)??§v????????¨??????p??????????????£?????????Node???????????????
pic.png?????§
?????§normalize????????§G?????????????????£???????????¨?????¨???

*/


#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}

namespace Normalize{
	template<class E>
	void dfs(vector<vector<E>>& G,vector<int>& ord, int v,int p=-1){
		ord.pb(v);
		int K = G[v].size();
		rep(i,K){
			if(G[v][i].to==p){
				rotate(G[v].begin()+i,G[v].begin()+i+1,G[v].end());
				K--;
				break;
			}
		}
		rep(i,K){
			dfs(G,ord,G[v][i].to,v);
		}
	}
	template<class E>
	vector<int> normalize_and_gettopord(vector<vector<E>>& G, int r=0){
		vector<int> ord;
		dfs(G,ord,r);
		return ord;
	}
}

/*
	Node + ???????????????????????????????????§??????(?¶????????????????????????????(?????????up????¶??????´????????????????????§??¨???))
*/
template<class N>
struct BidirectionalTreeDP{
	vector<N> dp;	//dp[v] <- u1,u2,... 			p????????£???v??????
	vector<N> up;	//up[v] <- v's brothers + pp 	v????????£???p??????
	vector<N> rp;	//dp[r] <- r????????¨?????????????????????

	vector<int> par;
	template<class E>
	BidirectionalTreeDP(vector<vector<E>>& G, int r=0){
		int V = G.size();
		dp.assign(V,N());
		up.assign(V,N());
		rp.assign(V,N());
		par.assign(V,0);

		vector<int> ord = Normalize::normalize_and_gettopord<E>(G,r);
		rep(t,V){
			int v = ord[t];
			if(v==r) par[v]=-1;
			else par[v]=G[v].back().to;
		}

		for(int t=V-1;t>=0;t--){	//dfs
			int v = ord[t];
			dp[v] = N();
			int K = G[v].size() - (v!=r);
			rep(i,K){
				const E& e = G[v][i];
				int u = e.to;
				dp[v] = dp[v] + dp[u].append_edge(v,e);
			}
			dp[v].finalize(v);
		}

		rep(t,V){					//ufs
			int v = ord[t];
			int K = G[v].size() - (v!=r);
			vector<N> ls(K+1),rs(K+1);
			rep(i,K){
				ls[i+1] = ls[i] + dp[G[v][i].to].append_edge(v,G[v][i]);
				rs[K-1-i] = dp[G[v][K-1-i].to].append_edge(v,G[v][K-1-i]) + rs[K-i];
			}
			rep(i,K){
				const E& e = G[v][i];
				int u = e.to;
				up[u] = ls[i] + rs[i+1];
				if(v!=r) up[u] = up[u] + up[v].append_edge(v,G[v].back());
				up[u].finalize(v);
			}
			rp[v] = ls[K];
			if(v!=r) rp[v] = rp[v] + up[v].append_edge(v,G[v].back());
			rp[v].finalize(v);
		}
	}

	N get(int v,int p=-1){	//p????????£???v??????
		if(p==-1) return rp[v];
		if(par[v]==p) return dp[v];
		return up[p];
	}
};

struct Node{	//p????????£???v???????????¨?????¨????????´???(??±?????????????????????)
	int dia;
	array<int,2> rd;
	Node(){
		dia=0;
		rd[0]=rd[1]=0;
	}

	/*
		???????????¨????£?
		e=(p -> this)??????????????????????????????
	*/
	template<class E>
	Node append_edge(int p,const E& e) const {
		Node n;
		n.rd[0] = rd[0] + e.dist;
		n.rd[1] = 0;
		n.dia = dia;
		return n;
	}
	Node operator+(const Node& r) const {
		Node n;
		vector<int> vc;
		rep(t,2) vc.pb(rd[t]),vc.pb(r.rd[t]);
		sort(all(vc),greater<int>());
		rep(t,2) n.rd[t]=vc[t];
		n.dia = max(dia,r.dia);
		return n;
	}
	void finalize(int r){
		chmax(dia,rd[0]+rd[1]);
	}
};
struct Edge{
	int to;
	int dist;
};
int main(){
	int N;
	cin>>N;
	vector<vector<Edge>> G(N);
	rep(i,N-1){
		int x,d;
		cin>>x>>d;
		int y = i+1;
		G[x].pb({y,d});
		G[y].pb({x,d});
	}

	BidirectionalTreeDP<Node> treedp(G);
	int ans = 0;
	rep(v,N){
		for(const Edge& e:G[v]){
			int u = e.to;
			chmax(ans,treedp.get(v,u).dia+e.dist);
		}
	}
	cout<<ans<<endl;
}