题目描述

该国有$\red{N}$个编号为$\red{1}$到$\red{N}$的城市，由$\red{N-1}$条无向道路连接，第$\red{i}$条道路连接城市$\red{i+1}$和城市$\red{a_i，}$ 经过道路$\red{i}$的费用为$\red{v_i}$。

小$\red{S}$想在这个国家进行一次旅行。出于他的强迫症，行程有如下限制：

旅行必须在城市$\red{1}$开始和结束。如果城市形成的树上有$\red{m}$片叶子结点，那么旅行的天数必须是$\red{m+1}$ 。每天结束时，除最后一天外，员工必须住在叶子城市的某家酒店。在整个行程中，员工必须在所有叶 子结点城市只停留一次。

在整个行程中，该国的所有道路必须正好经过两次。除第一天和最后一天外，小$\red{S}$需要自行支付的费用 为旅行期间单日发生的最大总通行费。剩余的通行费将由凉心出题人承担。

请帮助小$\red{S}$设计满足条件且费用旧能少的旅行。

输入格式

第一行输入一个整数 $\red{N}$。（$\red{2<N<131072）}$

第二行到第 $\red{N }$行每行输入两个整数，分别表示 $\red{a_i }$和 $\red{v_i}$。

输出格式

输出一个整数，表示最少费用。

样例

输入样例

7
1 1
1 1
2 1
2 1
3 1
3 1

输出样例

4

提示

对于$\red{9\%}$的数据，$\red{2<=N<=16 }$；

对于$\red{29\%}$的数据，$\red{2<=N<=2000 }$；

对于$\red{100\%}$的数据，$\red{2<=N<=131072,1<=a_i<=i,0<=v_i<=131072 }$。保证$\red{v_i}$是一个整数，给定的树是 一个完全二叉树。