Problem Description

E.Space likes to create Maximum Weight Independent Set problems.

Next, he wants to create $n$ Maximum Weight Independent Set problems.

E.Space has $n$ AIs, numbered $1 \sim n$.

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

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 in both directions. Besides these, no other pairs of AIs can communicate.

Each time, E.Space can choose an AI that currently stores a Maximum Weight Independent Set problem, publish the problem stored in it, and then clear the problem stored in that AI.

After E.Space publishes the problem and before clearing it, the AI will send this problem to all AIs that can communicate with it.

If an AI that receives this problem already has a Maximum Weight Independent Set problem stored, then it will merge the received problem with the one it already has, and store a new Maximum Weight Independent Set problem. Formally, if it originally stored a problem with difficulty $x$, and then receives a problem with difficulty $y$, then after merging it becomes a problem with difficulty $x+y$.

If an AI that receives the problem does not have any problem stored, then it will destroy the received information.

Due to the problem setter’s twisted mindset, E.Space wants the total difficulty sum of the $n$ Maximum Weight Independent Set problems he publishes to be as large as possible.

He wants you to help him solve this problem. He also says that if you successfully solve this problem in this training, then when publishing those $n$ Maximum Weight Independent Set problems, he will switch to your account in the last 10 minutes before the training ends and submit an official solution.

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$ integers, where the $i$-th one denotes $c_{i+1}$.

Output Format

Output one integer in one line, denoting the maximum possible total difficulty sum.

4
1 10 3 5
1 2 3

52

4
1 -2 5 5
1 2 2

27

Hint

Sample Explanation 1

One optimal publishing plan is as follows:

1. Publish the Maximum Weight Independent Set problem in the $2$-nd AI. The difficulty of this problem is $10$. After publishing, the difficulties of the problems stored in the $4$ AIs are $11,*,13,5$ ($*$ means that this AI has no Maximum Weight Independent Set problem stored, same below).

2. Publish the Maximum Weight Independent Set problem in the $3$-rd AI. The difficulty of this problem is $13$. After publishing, the difficulties of the problems stored in the $4$ AIs are $11,*,*,18$.

3. Publish the Maximum Weight Independent Set problem in the $1$-st AI. The difficulty of this problem is $11$. After publishing, the difficulties of the problems stored in the $4$ AIs are $*,*,*,18$.

4. Publish the Maximum Weight Independent Set problem in the $4$-th AI. The difficulty of this problem is $18$. After publishing, the difficulties of the problems stored in the $4$ AIs are $*,*,*,*$.

So the total difficulty sum of the $4$ problems is $10+13+11+18=52$.

Sample Explanation 2

One optimal publishing plan is as follows:

1. Publish the Maximum Weight Independent Set problem in the $3$-rd AI. The difficulty of this problem is $5$. After publishing, the difficulties of the problems stored in the $4$ AIs are $1,3,*,5$.

2. Publish the Maximum Weight Independent Set problem in the $4$-th AI. The difficulty of this problem is $5$. After publishing, the difficulties of the problems stored in the $4$ AIs are $1,8,*,*$.

3. Publish the Maximum Weight Independent Set problem in the $2$-nd AI. The difficulty of this problem is $8$. After publishing, the difficulties of the problems stored in the $4$ AIs are $9,*,*,*$.

4. Publish the Maximum Weight Independent Set problem in the $1$-st AI. The difficulty of this problem is $9$. After publishing, the difficulties of the problems stored in the $4$ AIs are $*,*,*,*$.

So the total difficulty sum of the $4$ problems is $5+5+8+9=27$.

Constraints

It is guaranteed that $\left|d_i\right| \le 10^9$, $1 \le c_i \lt i$, and $1 \le n \le 400$.

This problem uses bundled tests.

For subtasks with odd indices, it is guaranteed that $d_i \ge 0$.

Subtasks $1,2$ ($11 \times 2 = 22$ points): $n \le 9$.

Subtasks $3,4$ ($10 \times 2 = 20$ points): $n \le 19$.

Subtasks $5,6$ ($7 \times 2 = 14$ points): $n \le 50$, $c_i = i-1$.

Subtasks $7,8$ ($10 \times 2 = 20$ points): $c_i=i-1$.

Subtasks $9,10$ ($5 \times 2 = 10$ points): $n \le 50$.

Subtasks $11,12$ ($7 \times 2 = 14$ points): No special constraints.

Afterword

It is said that the difficulty of E.Space’s Maximum Weight Independent Set problems is taken as a logarithm?

It is said that E.Space wants to merge these $n$ problems into one single problem and publish it?

It is said that E.Space will not put these problems in the training?

Translated by ChatGPT 5