Largest Path Sum in Rooted Tree (Downward Only)

The tree is rooted at 0. Choose a non-empty path that only goes downward, edge by edge from parent to child, starting at any node, and find the maximum node sum. The path cannot pass through a node to join two subtrees.

输入格式

The first line contains n, the second line contains n parent entries, and the third line contains n value entries. 1≤n≤100000, parent[0]=−1, the others are in 0..n−1 and form a valid tree; values are in −1000..1000, and a parent index is not guaranteed to be smaller than its child's index.

输出格式

Output a single integer, the answer.

样例 1

输入：

5
-1 0 1 2 0
5 7 -10 4 15

输出：

20

样例 2

输入：

5
-1 0 1 2 0
-2 10 10 -3 10

输出：

20

样例 3

输入：

3
-1 0 0
-5 -2 -3

输出：

-2

样例说明

The outputs of the three public examples are, in order: 20; 20; -2. These answers were verified by independent enumeration or direct simulation.