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<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int N;
vector<pair<int,int> >G[1<<17];
pair<int,int>dp1[1<<17];
pair<int,int>dfs1(int u,int p)
{
	pair<int,int>ret;
	ret.first=ret.second=0;
	for(pair<int,int>q:G[u])
	{
		if(q.first==p)continue;
		pair<int,int>now=dfs1(q.first,u);
		ret.first=max(ret.first,now.first+q.second);
		ret.second=max(ret.second,max(now.second,q.second));
	}
	dp1[u]=ret;
	return ret;
}
int ans;
void dfs2(int u,int p,pair<int,int>P)
{
	vector<pair<pair<int,int>,int> >A;
	A.push_back(make_pair(P,-1));
	for(int i=0;i<G[u].size();i++)
	{
		int v=G[u][i].first;
		if(v==p)continue;
		A.push_back(make_pair(make_pair(dp1[v].first+G[u][i].second,max(dp1[v].second,G[u][i].second)),i));
	}
	sort(A.rbegin(),A.rend());
	pair<int,int>dmax1,dmax2,emax1,emax2;
	dmax1=dmax2=emax1=emax2=make_pair(0,-1);
	while(A.size()<3)A.push_back(make_pair(make_pair(0,0),-(int)A.size()-1));
	for(int i=0;i<A.size();i++)
	{
		ans=max(ans,A[i].first.second+A[i==0?2:0].first.first+A[i==1?2:1].first.first);
		if(dmax1.first<=A[i].first.first)
		{
			dmax2=dmax1;
			dmax1=make_pair(A[i].first.first,A[i].second);
		}
		else if(dmax2.first<=A[i].first.first)
		{
			dmax2=make_pair(A[i].first.first,A[i].second);
		}
		if(emax1.first<=A[i].first.second)
		{
			emax2=emax1;
			emax1=make_pair(A[i].first.second,A[i].second);
		}
		else if(emax2.first<=A[i].first.second)
		{
			emax2=make_pair(A[i].first.second,A[i].second);
		}
	}
	for(int i=0;i<G[u].size();i++)
	{
		if(G[u][i].first==p)continue;
		dfs2(G[u][i].first,u,make_pair(G[u][i].second+(dmax1.second==i?dmax2.first:dmax1.first),max(G[u][i].second,emax1.second==i?emax2.first:emax1.first)));
	}
}
int main()
{
	cin>>N;
	for(int i=1;i<N;i++)
	{
		int p,w;cin>>p>>w;
		G[p].push_back(make_pair(i,w));
		G[i].push_back(make_pair(p,w));
	}
	dfs1(0,-1);
	dfs2(0,-1,make_pair(0,0));
	cout<<ans<<endl;
}
