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>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,int> LP;
int n;
vector<P> G[100001];
ll one_max[100005];
ll two_max[100005];
ll ans=0;

ll dfs(int v,int p){
	ll val=0;
	for(int i=0;i<G[v].size();i++){
		int nv=G[v][i].first;
		if(nv==p)continue;
		val=max(val,(ll)dfs(nv,v)+G[v][i].second);
	}
	return (one_max[v]=val);
}

ll dfs2(int v,int p){
	ll val=0,val2=0;
	ll val3=0;
	for(int i=0;i<G[v].size();i++){
		int nv=G[v][i].first;
		if(nv==p)continue;
		val3=max((ll)dfs2(nv,v),val3);
		if(one_max[nv]+G[v][i].second>val2){
			val2=one_max[nv]+G[v][i].second
			;
			if(val2>val){
				swap(val2,val);
			}
		}
	}
	return (two_max[v]=max(val+val2,val3));
}

void dfs3(int v,int p,ll one_best,ll two_best){
	//printf("a %d %d %lld %lld\n",v,p,one_best,two_best);
	priority_queue<LP> one_que,two_que;
	one_que.push(LP(0,-1));
	one_que.push(LP(0,-1));
	two_que.push(LP(0,-1));
	for(int i=0;i<G[v].size();i++){
		int nv=G[v][i].first;
		if(nv==p)continue;
		//printf("push %lld %d\n",(ll)one_max[nv]+G[v][i].second,nv);
		one_que.push(LP(one_max[nv]+G[v][i].second,nv));
		two_que.push(LP(two_max[nv],nv));
	}
	for(int i=0;i<G[v].size();i++){
		int nv=G[v][i].first;
		if(nv==p)continue;
		bool one_flag=false;
		bool two_flag=false;
		if(one_que.top().second==nv){
			one_flag=true;
			one_que.pop();
		}
		LP tmp=one_que.top();
		one_que.pop();
		if(one_que.top().second==nv){
			one_flag=true;
			one_que.pop();
		}
		if(two_que.top().second==nv){
			two_flag=true;
			two_que.pop();
		}

		dfs3(nv,v,max(one_best,tmp.first)+G[v][i].second,max(max(two_best,tmp.first+one_que.top().first),two_que.top().first));
		ans=max(ans,(ll)two_max[nv]+G[v][i].second);
		ans=max(ans,(ll)one_best+tmp.first+G[v][i].second);
		ans=max(ans,(ll)tmp.first+one_que.top().first+G[v][i].second);
		ans=max(ans,(ll)max(two_best,two_que.top().first)+G[v][i].second);
		if(one_flag){
			one_que.push(LP(one_max[nv]+G[v][i].second,nv));
		}
		one_que.push(tmp);
		if(two_flag){
			two_que.push(LP(two_max[nv],nv));
		}
	}
}

int main(void){
	scanf("%d",&n);
	for(int i=0;i<n-1;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		G[i+1].push_back(P(a,b));
		G[a].push_back(P(i+1,b));
	}
	dfs(0,-1);
	dfs2(0,-1);
	dfs3(0,-1,0,0);
	printf("%lld\n",ans);
	return 0;
} 
