该国有N个编号为1到N的城市，由N-1条无向道路连接，第i条道路连接城市i+1和城市a_i，经过道路的费用为v_i。每个城市最多连接三个其他城市！

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

- 旅行必须在城市1开始和结束。

- 如果城市形成的树上有m片叶子结点，那么旅行的天数必须是m+1。

- 每天结束时，除最后一天外，员工必须住在叶子城市的某家酒店。

- 在整个行程中，员工必须在所有叶子结点城市只停留一次。

- 在整个行程中，该国的所有道路必须正好经过两次。

除第一天和最后一天外，小S需要自行支付的费用为旅行期间单日发生的最大总通行费。剩余的通行费将由凉心出题人承担。请帮助小S设计满足条件且费用尽可能少的旅行。

1. 第一行输入一个整数N。(2 < N < 131072)

2. 第二行到第N行每行输入两个整数，分别表示a_i和v_i。

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

- 对于9%的数据，特殊限制；

- 对于29%的数据，特殊限制；

- 对于100%的数据，2 < N < 131072。