Anton the Guard

Anton is a security guard responsible for $n$ objects numbered from $1$ to $n$. There are also $n-1$ roads, where the $i$-th road connects objects $u_i$ and $v_i$ and has a length of $w_i$. It is possible to reach any object from object $1$.

At the beginning, Anton is located at object $1$.

Let's define the priority of each object as the minimum number of roads that need to be traveled from this object to object $1$. For example, for object $1$ this number will be $0$; for all objects directly connected to $1$, it will be $1$, and so on.

Anton needs to visit all objects. He needs to first visit all objects that have a priority of $1$, then those that have a priority of $2$, and so on. If there are several objects with the same priority, Anton can choose the order in which to visit them. Note that he can only visit any object with priority $k$ after he has visited all objects with priority $k-1$.

Find the minimum distance that he will have to travel.

Input

The first line contains an integer $n$ ($1\le n\le 10^6$).

The second line contains $n-1$ integers $p_i$ which indicate that there is a road from object $i+1$ to object $p_i$ ($1\le p_i\le n$).

The third line contains $n-1$ integers $w_i$ which are the lengths of roads between objects $i+1$ and $p_i$ ($1\le w_i\le 10^9$).

It is guaranteed that it is possible to reach all other objects from object $1$.

Output

Output a single integer — the answer to the problem.

Examples

Scoring

1. ($4$ points): $1\le n\le 10$;

2. ($5$ points): $1\le n\le 22$;

3. ($13$ points): no more than $6$ objects have the same priority;

4. ($10$ points): no more than $10$ objects have the same priority;

5. ($15$ points): $w_i=1$;

6. ($15$ points): $1\le n\le 10^5$;

7. ($38$ points): without additional restrictions.