Level Up

Problem Description

The Arithmetic Coconut Median company has n employees. Every person has a direct supervisor except the boss. Boss's number is 1. Everyone has a Ability Value $A_{i}$. The wage of person i is the Median of Ability Value of person i and his (direct and indirect) subordinates. The ACM company decided to send a person to study in the center of the universe, then the Ability Value of this person will become 100000. Please calculate the maximum sum of wages of all people. Define the Median of t integers: the $\left \lceil \frac{t}{2} \right \rceil$ th smallest number of these t integers.

Input

The input contains multiple test cases. There are about 30 test cases. Each test case begin with an integer n. next line contains n integers $A_{1},A_{2}\cdots A_{n}$. next line contains n-1 integers $P_{2},P_{3}\cdots P_{n}. P_{i}$ indicates the direct supervisor of i. $1 \leq n \leq 100000$ $1 \leq A_{i} \leq 100000$ $1 \leq P_{i} < i$

Output

For each test case output a line contains an integer.

Sample Input

1
1
2
2 1
1
2
1 2
1

Sample Output

100000
100002
100001

Author

ZSTU

Source

2016 Multi-University Training Contest 5