Background

"It rains heavily during the Qingming Festival, and people on the road feel like breaking their souls."

There is no spring rain on the Qingming Festival. Under the cloud of flying snow, walking through the ice field, only the snowmobile carrying the meager hope of mankind.

The journey of $4.22$ light years, for the lonely traveler - earth, I am afraid it is also extremely lonely.

Description

Sulawesi was only a hundred kilometers away, and the air inside was colder than outside. Four pairs of eyes were glued to the screen in front of Alefin, the key program that controls the planetary engine: twelve rings of spring. He needs to deploy it into a chip in the power control system.

"Spring Festival twelve rings" is composed of $n$ subroutines, and the memory space required by the first $i$-th subroutine is $M_i$. The call relationships between the $n$ subroutines form a tree rooted in the $1$-st subroutine, where the $i$ subroutine's father on the call tree is the $f_i$-th subroutine.

Due to the shortage of memory, a memory segmentation mechanism is provided on the power control chip. You can divide the memory into segments $S_1, S_2,\cdots , S_k$, and preassigns each program to a fixed segment. If two subroutines have no direct or indirect calling relationship, they can be assigned to the same segment, but not vice versa. In other words, $a$ and $b$ can be assigned to the same segment if and only if $a$ and $b$ are not ancestor-descendant relationships on the call tree.

The size of a segment should be the maximum memory size required by all subprograms allocated to this segment, and the sum of all segment sizes cannot exceed the memory size of the system.

Now Alefin wants to know how much memory the power control chip needs to have in order for it to work correctly. That is, what is the minimum amount of memory required to divide the memory into segments and then allocate each subprogram to a segment so that there is no ancestor-descendant relationship between all subprograms allocated in each segment.

Format

Input

The first line contains a positive integer $n$ for the number of subroutines.

The second line has $n$ positive integers separated by Spaces $M_1,M_2,\cdots, M_n$, $M_i$ indicates the memory space required by the $i$-th subroutine.

The third line contains $n-1$ positive integers separated by Spaces $f_2, f_3,\cdots, f_n$, meets $f_i < i$, indicating that the father of the $i$-th subroutine in the call tree is the $f_i$-th subroutine.

Output

Only one integer, representing the minimum memory requirements.

Samples

5
10 20 20 30 30
1 1 2 2

60

In the optimal scenario, the memory is divided into three segments of the size $10$, $20$, and $30$, where the $1$-st subroutine is allocated in the $1$-st segment, the $2$-nd and $3$-rd subroutines are allocated in the $2$-nd segment, and the $4$-th and $5$-th subroutines are allocated in the $3$-rd segment. Arguably, there is no better solution.

10
2 1 1 1 1 2 1 1 1 2
1 1 1 4 5 3 3 4 3

6

15
10 1 10 10 2 6 9 6 8 6 3 4 4 5 5
1 2 2 1 5 4 4 1 2 10 1 9 6 1

31

Limitations

Testcase ID	$n$	$M$	Is a chain?
$1,2$	$\leq 5$	$\leq 10$	No
$3,4$	$\leq 10$	$\leq 2$
$5,6,7,8,9$	$\leq 16$	$\leq 10^9$
$10,11,12$	$\leq 2\times 10^5$		Yes
$13,14,15$	$\leq 2000$		No
$16,17,18,19,20$	$\leq 2\times 10^5$

Note: In the $10$-th, $11$-th, $12$-th testcases, the $1$-st subroutine is not necessarily an end point of the chain.

Where $M$ is the maximum of all child memory requirements, i.e. $\max\left\{M_i\right\}$.

For all data, $1 \leq n \leq 2 \times 10^5$, $1 \leq M \leq 10^9$.

After reading the problem carefully and analyzing the range of data, Alefin began writing a program to solve the problem.

$\texttt{\$ login Elephant}$

$\texttt{password: ********}$

Alefin, senior programmer. The third engineering group of Yuyang City reminds you:

• There are a lot of rules solving problems, and reading the statement is the first;

• If you don't program normatively, you will get no points and tears drop from your eyes.

$\texttt{\$ cd spring}$

$\texttt{\$ ac spring}$

$\texttt{Spring Accepted. Score: 100/100.}$