Little E likes to create Maximum Weight Independent Set problems.

He has come up with $n$ Maximum Weight Independent Set problems.

Unlike before, this time he wants to combine these $n$ problems into a single one.

Little E has $n$ AIs, numbered $1$ to $n$.

Initially, the $i$-th AI contains a Maximum Weight Independent Set problem with difficulty $d_i$ that Little E prepared in advance.

Some AIs can communicate with each other. For all $2 \le i \le n$, the $i$-th AI can communicate with the $c_i$-th AI, where $c_i < i$. Thus, these AIs form a tree structure. No other pairs of AIs can communicate.

Each time, Little E can choose an AI that contains a Maximum Weight Independent Set problem and combine it with the problems in all AIs that can communicate directly with it to form a new Maximum Weight Independent Set problem. When combining problems, there is always a loss in difficulty; it is impossible to simply add the difficulties of all problems together. The difficulty of this new Maximum Weight Independent Set problem is the sum of the difficulties of the problems in all AIs that can communicate directly with it, minus the difficulty of the problem originally stored in the chosen AI. After this, the difficulties of the problems in all AIs that can communicate directly with the chosen AI become $0$.

Little E wants to perform a series of operations to make the problem difficulties in $n-1$ AIs equal to $0$, and then release the problem in the last remaining AI.

Due to the setter's twisted nature, Little E wants to maximize the difficulty of the final Maximum Weight Independent Set problem.

He wants you to help him solve this problem, and he says that if you succeed, he will help you submit a reference solution when he releases that Maximum Weight Independent Set problem.

Input

The first line contains a positive integer $n$.

The second line contains $n$ integers, where the $i$-th integer represents $d_i$.

The third line contains $n-1$ positive integers, where the $i$-th integer represents $c_{i+1}$.

Output

A single integer representing the answer.

Examples

Input 1

4
-1 2 3 4
1 1 1

Output 1

10

Subtasks

It is guaranteed that $1 \le n \le 351493$.

It is guaranteed that $1 \le c_i < i$.

It is guaranteed that $|d_i| \le 10^9$.

• Subtask 1 (13 points): $c_i = i-1$
• Subtask 2 (6 points): $d_i > 0$
• Subtask 3 (11 points): $n \le 7$
• Subtask 4 (13 points): $n \le 16$
• Subtask 5 (22 points): $n \le 100$
• Subtask 6 (35 points): No special properties