描述

在NS有N个教室，编号为1 ~ N，由N - 1个双向道路连接。没错就是一个树的结构。我们将1号结点设为机房，树是棵完全二叉树（当且仅当树中的每个非叶顶点都有两个孩子时，树是一个完整的二叉树）。道路编号为1 ~ N -1.第i条道路连接教室i + 1和教室ai。当通过时会有x个dalao把守在道路上，zm会受到暴击伤害，加重x点伤势。
在每个叶子结点都埋藏有一颗龙珠，zm到达叶子结点时，龙珠会发动自己魔力清空他的伤势，当集齐每个叶子结点的龙珠时，zm就可以召唤魔法阵逃离NS。
但是龙珠发动也有个条件，就是zm必须经过每条道路恰好两次。
（不可忽视的提示：可爱的ggr心疼zm 1e - 18 ms，于是免除了zm从机房到达到第一个叶子结点和从最后一个叶子结点出发回到机房中的伤势）
zm现在想知道除了自己被免除的两次伤害中，他逃离NS过程中到达每个叶子结点受到的最大的伤势最小会是多少?(因为他好提前做好准备以防逃不到叶子结点就GG了)

输入格式

第一排一个数n（ n <= 131072）表示有n个教室。
接下来n - 1排 每行两个数 ai （ai <= n） x（0 <= x <= 131072），表示第i条道路连接教室 i + 1 和 ai，有x个dalao把守

输出格式

一个数表示zm逃离过程中受到的最大伤势的最小值

样例

样例输入1

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

样例输出1

4

样例输入2

9
1 2
1 2
3 2
3 2
5 2
5 2
7 2
7 2

样例输出2

6

样例输入3

15
1 2
1 5
3 3
4 3
4 3
6 5
5 4
5 3
6 3
3 2
11 5
11 3
13 2
13 1

样例输出3

15

样例输入4

3
1 0
1 0

样例输出4

0