It is 100 kilometers to Sulawesi, and the air inside the vehicle is colder than outside. Four pairs of eyes are fixed on the screen in front of Elephant; it is the critical program for controlling the planetary engine: "Spring Twelve Echoes." He needs to deploy it onto a chip in the power control system.

"Spring Twelve Echoes" consists of $n$ subroutines, and the memory space required by the $i$-th subroutine is $M_i$. The calling relationships between these $n$ subroutines form a tree rooted at the first subroutine, where the parent of the $i$-th subroutine in the calling tree is the $f_i$-th subroutine.

Due to limited memory, the power control chip provides a memory segmentation mechanism. You can divide the memory into several segments $S_1, S_2, \dots, S_k$ and pre-assign each program to a fixed segment. If two subroutines do not have a direct or indirect calling relationship, they can be assigned to the same segment; otherwise, they cannot. In other words, $a$ and $b$ can be assigned to the same segment if and only if $a$ and $b$ do not have an ancestor-descendant relationship in the calling tree.

The size of a segment is the maximum of the memory requirements of all subroutines assigned to that segment. The sum of the sizes of all segments cannot exceed the system's total memory.

Now, Elephant wants to know the minimum amount of memory the power control chip must have to ensure the correct operation of "Spring Twelve Echoes." That is, what is the minimum total memory required to divide the memory into several segments and assign each subroutine to a segment such that no two subroutines assigned to the same segment have an ancestor-descendant relationship?

Input

The input is read from the file spring.in.

The first line contains a positive integer $n$, representing the number of subroutines, where $n \le 2 \times 10^5$.

The second line contains $n$ space-separated positive integers $M_1, M_2, \dots, M_n$, where $M_i$ represents the memory space required by the $i$-th subroutine.

The third line contains $n-1$ space-separated positive integers $f_2, f_3, \dots, f_n$, satisfying $f_i < i$, representing that the parent of the $i$-th subroutine in the calling tree is the $f_i$-th subroutine.

Output

Output to the file spring.out.

A single integer representing the minimum memory requirement.

Examples

Input 1

5
10 20 20 30 30
1 1 2 2

Output 1

60

Note 1

In the optimal solution, the memory is divided into three segments of sizes 10, 20, and 30. The 1st subroutine is assigned to the first segment, the 2nd and 3rd subroutines are assigned to the second segment, and the 4th and 5th subroutines are assigned to the third segment. It can be proven that no better solution exists.

Input 2

(See spring/spring2.in in the contestant directory)

Output 2

(See spring/spring2.ans in the contestant directory)

Input 3

(See spring/spring3.in in the contestant directory)

Output 3

(See spring/spring3.ans in the contestant directory)

Subtasks

Note: In test cases 10, 11, and 12, the 1st subroutine is not necessarily an endpoint of the chain. Here, $M$ is the maximum of all memory requirements, i.e., $\max\{M_i\}$. For all data, $1 \le n \le 2 \times 10^5$, $1 \le M \le 10^9$.

Hint

Elephant, after carefully reading the problem and analyzing the data constraints, began writing a program to solve this problem.

$ login Elephant
password: ********
Elephant, senior programmer. The Yuyang City Third Engineering Team reminds you:
- There are thousands of ways to solve problems, reading the problem is the first one;
- Non-standard programming leads to tears of zero points.
$ cd spring
$ ac spring
Spring Accepted. Score: 100/100.