Problem Description

Xiao E likes to create Maximum Weight Independent Set problems.

Next, he came up with $n$ Maximum Weight Independent Set problems.

But unlike before, this time he wants to merge these $n$ problems into a single problem.

Xiao E has $n$ AIs, numbered from $1$ to $n$.

At the beginning, the $i$-th AI stores one Maximum Weight Independent Set problem prepared in advance by Xiao E, with difficulty $d_i$.

Some AIs can communicate with each other. For all $2 \le i \le n$, the $i$-th AI can communicate directly with the $c_i$-th AI, where $c_i<i$. Therefore, these AIs form a tree. In addition, any other pairs of AIs cannot communicate with each other directly.

Each time, Xiao E can choose an AI that currently stores a Maximum Weight Independent Set problem, and merge it with all problems on AIs that can communicate directly with it, forming a new Maximum Weight Independent Set problem. When merging, there is always a loss of difficulty, so it is impossible to simply add up all difficulties. The difficulty of the new Maximum Weight Independent Set problem equals the sum of the difficulties of the problems on those AIs that can communicate directly with it, minus the difficulty of the problem originally stored on the chosen AI. Then, the difficulties of the problems on those directly communicating AIs become $0$.

Xiao E wants to perform several operations so that the problem difficulties on $n-1$ AIs all become $0$, and then publish the final problem stored in the last remaining AI.

Due to the problem setter's twisted mindset, Xiao E wants the difficulty of the final Maximum Weight Independent Set problem to be as large as possible.

He asks you to help solve this problem, and says that if you succeed, then when publishing that Maximum Weight Independent Set problem, he will help you submit a reference solution code.

Input Format

The first line contains a positive integer $n$.

The second line contains $n$ integers, where the $i$-th one denotes $d_i$.

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

Output Format

Output one integer in a single line, representing the answer.

4
-1 2 3 4
1 1 1

10

Hint

Constraints: $1\le n\le 351493$.

Constraints: $1\le c_i <i$.

Constraints: $|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.

Translated by ChatGPT 5