Pretty Painting

Valerio is drawing his (rooted) Christmas tree to celebrate his favorite holiday. Being a computer scientist, his tree has $N$ nodes, numbered from $0$ to $N-1$, with node $0$ being the root. Each other node is connected to its parent $P_i$ by an edge of length $W_i$.

Task

Valerio now wants to color some of the edges to make his drawing look more similar to the original subject. He also wants to avoid making the drawing too chaotic, therefore each node $i$ can have at most $K_i$ incident colored edges. What is the maximum total length of colored edges he can achieve?

Input data

The input file consists of:

• a line containing integer $N$.
• a line containing the $N$ integers $K_{0}, \, \ldots, \, K_{N-1}$.
• a line containing the $\mathtt{N - 1}$ integers $P_{1}, \, \ldots, \, P_{N-1}$.
• a line containing the $\mathtt{N - 1}$ 64-bit integers $W_{1}, \, \ldots, \, W_{N-1}$.

Output data

The output file must contain a single line consisting of 64-bit integer $\mathtt{ans}$.

Constraints and clarifications

• $1 \le N \le 100 \ 000$.
• $0 \le K_i < N$ for each $i=0\ldots N-1$.
• $0 \le P_i < i$ for each $i=1\ldots N-1$.
• $0 \le W_i \le 1 \ 000 \ 000 \ 000$ for each $i=1\ldots N-1$.

Example 1

stdin

5
1 1 1 1 1
0 0 1 1
4 2 3 5

stdout

7

Explanation

The tree in the first sample case is depicted below.

The optimal solution consists in coloring the edge between nodes $0$ and $2$ and the one between nodes $1$ and $4$, as shown below, with a total length of $7$.

Example 2

stdin

7
1 2 2 1 1 1 1
0 0 1 1 2 2
8 7 6 6 3 4

stdout

23

Explanation

In the second sample case, the optimal solution consists in coloring the edges $(0,2)$, $(1,3)$, $(1,4)$ and $(2,6)$, for a total length of $23$.