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

#include <bits/stdc++.h>
#ifdef LOCAL
#include "dump.hpp"
#else
#define dump(...)
#endif

#define BEGIN_STACK_EXTEND(size) void * stack_extend_memory_ = malloc(size);void * stack_extend_origin_memory_;char * stack_extend_dummy_memory_ = (char*)alloca((1+(int)(((long long)stack_extend_memory_)&127))*16);*stack_extend_dummy_memory_ = 0;asm volatile("mov %%rsp, %%rbx\nmov %%rax, %%rsp":"=b"(stack_extend_origin_memory_):"a"((char*)stack_extend_memory_+(size)-1024));

#define END_STACK_EXTEND asm volatile("mov %%rax, %%rsp"::"a"(stack_extend_origin_memory_));free(stack_extend_memory_);

using namespace std;

template<class T> inline void chmax(T &a, const T &b) { if(a < b) a = b; }
template<class T> inline void chmin(T &a, const T &b) { if(a > b) a = b; }

template<class T, class U> inline void fill_array(T &e, const U &v) { e = v; }
template<class T, class U, size_t s> inline void fill_array(T (&a)[s], const U &v) {for(auto&e:a)fill_array(e,v);}
template<class T, class U, size_t s> inline void fill_array(array<T, s> &a, const U &v) {for(auto&e:a)fill_array(e,v);}
template<class T, class U> inline void fill_array(vector<T> &a, const U &v) {for(auto&e:a)fill_array(e,v);}

// * solve

constexpr int MAX_N = 100000;

vector<pair<int, int>> G[MAX_N];
int max_down[MAX_N];
int max_under[MAX_N];

void dfs(const int v = 0, const int p = -1) {
	array<int, 2> mx;
	mx.fill(0);
	for(const auto &e : G[v]) {
		const int u = e.second;
		const int w = e.first;
		if(u == p) continue;

		dfs(u, v);
		int x = max_down[u] + w;
		chmax(max_down[v], x);
		chmax(max_under[v], max_under[u]);

		for(auto &m : mx) {
			if(m < x) swap(m, x);
		}
	}
	chmax(max_under[v], mx[0] + mx[1]);
}

int dfs2(const int v = 0, const int p = -1, const int up = 0, const int above = 0) {
	int res = 0;

	array<pair<int, int>, 2> mx_cycle;
	mx_cycle.fill(make_pair(0, -1));
	mx_cycle[0] = make_pair(above, p);

	array<pair<int, int>, 3> mx;
	mx.fill(make_pair(0, -1));
	mx[0] = make_pair(up, p);

	for(const auto &e : G[v]) {
		const int u = e.second;
		const int w = e.first;
		if(u == p) continue;

		pair<int, int> x = make_pair(max_under[u], u);
		for(auto &m : mx_cycle) {
			if(m < x) swap(m, x);
		}

		x = make_pair(max_down[u] + w, u);
		for(auto &m : mx) {
			if(m < x) swap(m, x);
		}
	}

	for(const auto &e : G[v]) {
		const int u = e.second;
		const int w = e.first;
		if(u == p) continue;

		int longest_cycle = (u == mx_cycle[0].second ? mx_cycle[1].first : mx_cycle[0].first);
		if(u == mx[0].second) {
			chmax(longest_cycle, mx[1].first + mx[2].first);
			chmax(res, dfs2(u, v, mx[1].first + w, longest_cycle));
		}
		else if(u == mx[1].second) {
			chmax(longest_cycle, mx[0].first + mx[2].first);
			chmax(res, dfs2(u, v, mx[0].first + w, longest_cycle));
		}
		else {
			chmax(longest_cycle, mx[0].first + mx[1].first);
			chmax(res, dfs2(u, v, mx[0].first + w, longest_cycle));
		}

		chmax(longest_cycle, max_under[u]);
		chmax(res, longest_cycle + w);
	}

	return res;
}

int main(int argc, const char *const argv[]) {
	BEGIN_STACK_EXTEND(128*1024*1024);

#ifdef LOCAL
	init_debug(argc, argv);
#endif

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int n;
	cin >> n;

	for(int v = 1; v < n; ++v) {
		int p, w;
		cin >> p >> w;
		G[v].emplace_back(w, p);
		G[p].emplace_back(w, v);
	}

	dfs();

	for(int v = 0; v < n; ++v) {
		dump(max_under[v]);
	}

	cout << dfs2() << endl;

	END_STACK_EXTEND;
	return EXIT_SUCCESS;
}