There are $N$ cities in the country of JOI, numbered from $1$ to $N$. Between these cities, there are $N - 1$ roads, numbered from $1$ to $N - 1$.
Road $i$ $(1 \le i \le N - 1)$ connects city $P_i$ $(P_i \le i)$ and city $i + 1$ bidirectionally. It is guaranteed that every city is reachable from city $1$ by passing through some roads.

In addition, there are $N - 1$ rivers running parallel to the roads, numbered from $1$ to $N - 1$.
River $i$ $(1 \le i \le N - 1)$ runs parallel to road $i$, and flows from city $P_i$ toward city $i + 1$.

Each of the $N$ cities has exactly one lamp installed. Each lamp has a certain strength.
If the lamp in city $t$ $(1 \le t \le N)$ has strength $l$, then all cities that can be reached from city $t$ by passing through fewer than $l$ roads are illuminated by that lamp.

Initially, all lamp strengths are $0$, and no city is illuminated.

You may perform river rafting any number of times (possibly zero).
Each rafting starts at city $1$. First, you increase the strength of the lamp at city $1$ by $1$. Then, you repeatedly perform the following operations in order:

1. Decide whether to end the rafting. However, if there is no river flowing out of the current city, you must end the rafting.
2. If you continue the rafting, choose one of the rivers flowing out of the current city and move along the direction of the river. Increase the strength of the lamp at the destination city by $1$.

If you end a rafting at city $t$, the cost of this rafting is $C_t$.

By performing river rafting any number of times, you want to ensure that every city is illuminated by at least one lamp. Among all such ways, minimize the total cost of the raftings.

Given the information about the roads and the costs, write a program to compute the minimum possible total cost required so that every city is illuminated by at least one lamp.

Input

The input is given from standard input in the following format:

$N$

$P_1\ P_2\ \cdots\ P_{N-1}$

$C_1\ C_2\ \cdots\ C_N$

Output

Print the minimum total cost required so that every city is illuminated by at least one lamp.

Constraints

• $2 \le N \le 700$.
• $1 \le P_i \le i$ $(1 \le i \le N - 1)$.
• $1 \le C_t \le 10^9$ $(1 \le t \le N)$.
• All input values are integers.

Scoring

1. (13 points) $N \le 8$.
2. (25 points) $N \le 100$.
3. (7 points) $P_i = 1$ $(1 \le i \le N - 1)$.
4. (11 points) $P_i = i$ $(1 \le i \le N - 1)$.
5. (16 points) For every $i$ $(1 \le i \le N)$, there are at most two indices $j$ $(1 \le j \le N - 1)$ such that $P_j = i$.
6. (28 points) No additional constraints.

Example

Example 1

Input

5
1 2 2 4
10 4 8 9 5

Output

9

In the first rafting, choose river $1$ and end at city $2$.
The strengths of the lamps at cities $1$ and $2$ increase by $1$, and the cost is $4$.

In the second rafting, choose rivers $1$, $3$, and $4$, and end at city $5$.
The strengths of the lamps at cities $1$, $2$, $4$, and $5$ increase by $1$, and the cost is $5$.

After these operations: - The strengths of the lamps at cities $1$ and $2$ are $2$, - The strength at city $3$ is $0$, - The strengths at cities $4$ and $5$ are $1$.

Cities $1$, $2$, $3$, and $4$ are illuminated by the lamp of strength $2$ at city $2$, and city $5$ is illuminated by the lamp of strength $1$ at city $5$.

Thus, all cities are illuminated, and the total cost is $4 + 5 = 9$.
It is impossible to satisfy the condition with a total cost less than $9$, so the answer is $9$.

This example satisfies the constraints of Subtasks 1, 2, 5, and 6.

Example 2

Input

9
1 1 1 2 5 5 5 3
100 70 80 90 60 30 40 50 30

Output

90

Perform the rafting that goes through rivers $1$, $4$, and $5$, and ends at city $6$, twice.
Also perform the rafting that goes through rivers $2$ and $8$, and ends at city $9$, once.

After these operations: - The strength of the lamp at city $1$ is $3$, - The strengths at cities $2$, $5$, and $6$ are $2$, - The strengths at cities $3$ and $9$ are $1$, - The strengths at cities $4$, $7$, and $8$ are $0$.

All cities are illuminated by some lamp.
The total cost is $30 \times 2 + 30 = 90$.

It is impossible to satisfy the condition with a total cost less than $90$, so the answer is $90$.

This example satisfies the constraints of Subtasks 2 and 6.