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;

struct Edge{
	int to;
	int weight;
};
vector<Edge> g[100010];
vector<Edge> ch[100010];


void buildTree(int x,int p=-1){
	struct HOGE{
		int sid;
		pair<int,int> argv;
	};
	stack<HOGE> S;
	S.push({0,{x,p}});
	while( S.size() ){
		HOGE s = S.top(); S.pop();
		tie(x,p) = s.argv;
		for( auto e : g[x] ){
			if( e.to != p ){
				S.push({0,{e.to,x}});
				ch[x].push_back(e);
			}
		}
	}
}

struct Info{
	int chid;
	int len;
};
bool operator < (const Info &a,const Info &b){
	if( a.len == b.len ) return a.chid < b.chid;
	return a.len < b.len;
}


vector<Info> seq[100010];
int diameter[100010]; 
int maxPath[100010];

void calcDiameter(int x){
	struct HOGE{
		int sid;
		int argv;
	};
	stack<HOGE> S;
	S.push({0,x});

	while( S.size() ){
		HOGE s = S.top(); S.pop();
		x = s.argv;
		if( s.sid == 0 ){
			S.push({1,x});
			for( auto e : ch[x] ){	
				S.push({0,e.to});
			}
		}else if( s.sid == 1 ){
			vector<Info> s;
			for( auto e : ch[x] ){
				diameter[x] = max(diameter[x],diameter[e.to]);
				s.push_back({e.to,maxPath[e.to]+e.weight});
			}
			
			sort(s.rbegin(),s.rend());
			if( s.size() == 1 ){
				diameter[x] = max(diameter[x],s[0].len);
			}else if( s.size() >= 2 ){
				diameter[x] = max(diameter[x],s[0].len+s[1].len);
			}
			seq[x] = s;
			maxPath[x] = s.size() >= 1 ? s[0].len : 0;
		}
	}
}


struct ImportantInfo{
	int pathMax;
	int diameterMax;
};

vector<Info> getMaxTwo(const vector<Info> &s,int cid){
	vector<Info> own;
	for(int i = 0 ; i < s.size() ; i++){
		if( cid != s[i].chid ) own.push_back(s[i]);
		if( own.size() >= 2 ) break;
	}
	return own;
}

int ans = 0;
void dfs(int x,ImportantInfo info){
	struct HOGE{
		int sid;
		pair<int,ImportantInfo> argv;
	};
	stack<HOGE> S;
	S.push({0,{x,info}});

	while( S.size() ){
		HOGE s = S.top(); S.pop();
		tie(x,info) = s.argv;
		for( auto e : ch[x] ){
			vector<Info> goodPaths = getMaxTwo(seq[x],e.to);
			goodPaths.push_back({-1,info.pathMax});
			goodPaths.push_back({-1,0});
			sort(goodPaths.rbegin(),goodPaths.rend());
			ImportantInfo nextInfo = info;
			nextInfo.pathMax = max(nextInfo.pathMax,goodPaths[0].len) + e.weight;
			nextInfo.diameterMax = max(nextInfo.diameterMax,goodPaths[0].len+goodPaths[1].len);
			ans = max(ans,max(diameter[e.to],nextInfo.diameterMax) + e.weight);
			S.push({0,{e.to,nextInfo}});
		}
	}


}

int main(){
	int N;
	cin >> N;
	for(int i = 1 ; i < N ; i++){
		int p,w;
		cin >> p >> w;
		g[p].push_back({i,w});
		g[i].push_back({p,w});
	}
	int root = 0;
	buildTree(root);
	calcDiameter(root);
	dfs(root,{0,0});
	/*for(int i = 0 ; i < N ; i++){
		cout << i << ": " << diameter[i] << "|";
		for(auto j : seq[i] ) cout << j.len << " ";
		cout << endl;
	}*/
	cout << ans << endl;

}