D--树的最大权值和

Time Limit: 2000 ms Memory Limit: 65536 KiB

Problem Description

给出一棵含有n个点的树,每个点权值为wi,求从根节点到叶子结点权值和最大的那条路经的权值和是多少。

Input

多组输入。

对于每组输入:

第一行,一个整数n(1<= n && n <= 10000)

接下来2n+1行,每行两个整数fw(w <= 1000)

i+1表示第i个节点的父节点为f,权值为w,若 f == 0,则表示i为根节点。 约有600组数据。

Output

 对于每组数据,输出一个数代表答案。

Sample Input

3
0 5
1 5
1 6

Sample Output

11

Hint

 

Source

zmx