Given a rooted tree with $n$ nodes, where node $1$ is the root. Each node $i$ has a weight $w_i$.

Find an optimal DFS traversal order to maximize $\sum\limits_{i=1}^n p_iw_i$, where $p_i$ is the time at which node $i$ is visited, representing the number of distinct nodes visited up to and including node $i$ for the first time.

Input

The input is read from standard input.

The first line contains a positive integer $n$ ($1 \le n \le 2 \times 10^5$).

The second line contains $n$ positive integers, where the $i$-th integer represents $w_i$ ($1 \le w_i \le 10^8$).

The third line contains $n-1$ positive integers, where the $i$-th integer represents the parent of node $i+1$, guaranteed to be in the range $1 \sim i$.

Output

Output to standard output.

A single integer representing the maximum value of $\sum\limits_{i=1}^n p_iw_i$.

Examples

Input 1

5
8 5 3 6 4
1 1 3 3

Output 1

75

Note 1

The traversal order $(1, 3, 5, 4, 2)$ yields the maximum value $1 \times 8 + 2 \times 3 + 3 \times 4 + 4 \times 6 + 5 \times 5 = 75$.

Note that $(1, 3, 2, 4, 5)$ is not a valid DFS traversal order.