Sewer Drainage Partition

The tree is rooted at 0, and each node has a direct inflow. Cut exactly one parent-child edge to split the tree into two parts, minimizing the absolute difference between the two parts' total direct inflow.

输入格式

The first line contains n, the second line contains n values of parent, and the third line contains n direct inflows. Complete original bounds: 2≤n≤100000, inflow 1..10000, parent[0]=−1, 0≤parent[i]<i, and the tree depth is at most 500.

输出格式

Output one integer answer.

样例 1

输入：

6
-1 0 0 1 1 2
1 2 2 1 1 1

输出：

0

样例 2

输入：

4
-1 0 1 2
1 4 3 4

输出：

2

样例 3

输入：

2
-1 0
10000 1

输出：

9999

样例说明

The outputs of the three public examples are, in order: 0; 2; 9999. They have been checked by independent enumeration or direct simulation.