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 <utility>
#include <tuple>
#include <algorithm>
#include <type_traits>
#include <queue>
#include <functional>
#include <vector>
#include <string>
#include <stack>
#include <iostream>
namespace lc {
template <class WeightType>
struct EdgeWithWeight {
	int to;
	WeightType weight;
	EdgeWithWeight(int to, const WeightType &weight)
		: to(to), weight(weight)
	{ }
};
}
namespace lc {
template <typename EdgeType>
class AdjacencyList {
public:
	typedef std::vector<EdgeType> ListType;
private:
	std::vector<ListType> m_lists;
public:
	explicit AdjacencyList(int n = 0)
		: m_lists(n)
	{ }
	template <typename... Args>
	void add_edge(int u, Args&&... args){
		m_lists[u].emplace_back(args...);
	}
	ListType &operator[](int u){ return m_lists[u]; }
};
}
namespace lc {
template <class T, int K, class Comparator = std::less<T>>
class TopK {
private:
	Comparator m_comparator;
	int m_count;
	T m_buffer[K];
public:
	explicit TopK(const Comparator &cmp = Comparator())
		: m_comparator(cmp)
		, m_count(0)
		, m_buffer()
	{ }
	void insert(const T &x){
		if(m_count == K && m_comparator(m_buffer[K - 1], x)){ return; }
		if(m_count < K){ ++m_count; }
		m_buffer[m_count - 1] = x;
		for(int i = m_count - 2; i >= 0; --i){
			if(m_comparator(m_buffer[i + 1], m_buffer[i])){
				std::swap(m_buffer[i + 1], m_buffer[i]);
			}
		}
	}
	const T &operator[](size_t i) const { return m_buffer[i]; }
	size_t size() const { return m_count; }
};
}
using namespace std;
typedef pair<int, int> pii;
typedef lc::EdgeWithWeight<int> Edge;
typedef lc::TopK<pii, 3, greater<pii>> Top3p;
lc::AdjacencyList<Edge> graph;
void solve_first(vector<Top3p> &result, int u, int p){
	result[u].insert(pii(0, u));
	for(const auto &e : graph[u]){
		const int v = e.to;
		if(v == p){ continue; }
		solve_first(result, v, u);
		result[u].insert(pii(result[v][0].first + e.weight, v));
	}
}
void solve_second(vector<Top3p> &result, int u, int p, int w){
	if(p >= 0){
		if(result[p][0].second != u){
			result[u].insert(pii(result[p][0].first + w, p));
		}else if(result[p].size() >= 2){
			result[u].insert(pii(result[p][1].first + w, p));
		}
	}
	for(const auto &e : graph[u]){
		const int v = e.to;
		if(v == p){ continue; }
		solve_second(result, v, u, e.weight);
	}
}
int solve_third(
	vector<Top3p> &result, int u, int p,
	const vector<Top3p> &table)
{
	result[u].insert(pii(0, u));
	for(const auto &e : graph[u]){
		const int v = e.to;
		if(v == p){ continue; }
		const auto t = solve_third(result, v, u, table);
		result[u].insert(pii(max(result[v][0].first, t), v));
	}
	int sum = 0;
	for(int i = 0, done = 0; done < 2 && i < table[u].size(); ++i){
		if(table[u][i].second == p){ continue; }
		sum += table[u][i].first;
		++done;
	}
	return sum;
}
void solve_forth(
	vector<Top3p> &result, int u, int p,
	const vector<Top3p> &table)
{
	if(p >= 0){
		int maxval = 0;
		for(int i = 0, done = 0; done < 2 && i < table[p].size(); ++i){
			if(table[p][i].second == u){ continue; }
			maxval += table[p][i].first;
			++done;
		}
		for(int i = 0; i < result[p].size(); ++i){
			if(result[p][i].second != u){
				maxval = max(maxval, result[p][i].first);
			}
		}
		result[u].insert(pii(maxval, p));
	}
	for(const auto &e : graph[u]){
		const int v = e.to;
		if(v == p){ continue; }
		solve_forth(result, v, u, table);
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	graph = lc::AdjacencyList<Edge>(n);
	for(int i = 1; i < n; ++i){
		int p, w;
		cin >> p >> w;
		graph.add_edge(i, p, w);
		graph.add_edge(p, i, w);
	}
	vector<Top3p> table1(n);
	solve_first(table1, 0, -1);
	solve_second(table1, 0, -1, 0);
	vector<Top3p> table2(n);
	solve_third(table2, 0, -1, table1);
	solve_forth(table2, 0, -1, table1);
	int answer = 0;
	for(int u = 0; u < n; ++u){
		for(const auto &e : graph[u]){
			const int v = e.to;
			int local = e.weight;
			for(int i = 0, j = 0; j < 2 && i < table1[v].size(); ++i){
				if(table1[v][i].second == u){ continue; }
				local += table1[v][i].first;
				++j;
			}
			answer = max(answer, local);
			for(int i = 0; i < table2[u].size(); ++i){
				if(table2[u][i].second != v){
					answer = max(answer, table2[u][i].first + e.weight);
				}
			}
		}
	}
	cout << answer << endl;
	return 0;
}