题目描述

E.Space 喜欢出最大权独立集问题。

接下来，他还想出 $n$ 道最大权独立集问题。

E.Space 有 $n$ 个 AI，编号为 $1\sim n$。

开始第 $i$ 个 AI 里面存有一道 E.Space 事先出好的一道难度为 $d_i$ 的最大权独立集问题。

有些 AI 之间可以互相通信，对于所有的 $2 \le i \le n$，第 $i$ 个 AI 可以和第 $c_i$ 个 AI 互相通信。此外，其他对 AI 不可以互相通信。

E.Space 每次可以选择一个存有一道最大权独立集问题的 AI，把存在里面的题出出来，然后清除存在这个 AI 里的题。

在 E.Space 出题之后清除题目之前，AI 会把这道题发给能和它通信的所有 AI。

如果一个收到这道题的 AI 中已经存有一道最大权独立集问题，那么这个 AI 会把这个收到的题和原本存有的题结合起来，变成一道新的最大权独立集问题存起来。形式化地，如果这个 AI 原来存了一道难度为 $x$ 的最大权独立集问题，接着收到了一道难度为 $y$ 的最大权独立集问题，那么结合之后是一道难度为 $x+y$ 的最大权独立集问题。

如果一个收到题的 AI 中未存有题，那么这个 AI 会销毁收到的这个信息。

由于出题人的丧病心理，E.Space 想要出出来的 $n$ 道最大权独立集问题的难度之和尽量大。

他想叫你帮他解决这个问题，还说如果你成功在这场训练中解决了这个问题，那么在出那 $n$ 道最大权独立集问题的时候，他会在训练结束前 10 分钟切换至你的账号然后提交一份标程代码。

输入格式

第一行一个正整数 $n$。

第二行 $n$ 个整数，第 $i$ 个表示 $d_i$。

第三行 $n-1$ 个整数，第 $i$ 个表示 $c_{i+1}$。

输出格式

一行一个整数，表示最大的难度之和。

4
1 10 3 5
1 2 3

52

4
1 -2 5 5
1 2 2

27

提示

【样例解释 1】

一种最优的出题方案如下：

1. 出第 $2$ 个 AI 中的最大权独立集问题，此时该题难度为 $10$，出题后 $4$ 个 AI 中的最大权独立集问题的难度分别为 $11,*,13,5$ ($*$ 表示该 AI 中没有最大权独立集问题，下同)。

2. 出第 $3$ 个 AI 中的最大权独立集问题，此时该题难度为 $13$，出题后 $4$ 个 AI 中的最大权独立集问题的难度分别为 $11,*,*,18$。

3. 出第 $1$ 个 AI 中的最大权独立集问题，此时该题难度为 $11$，出题后 $4$ 个 AI 中的最大权独立集问题的难度分别为 $*,*,*,18$。

4. 出第 $4$ 个 AI 中的最大权独立集问题，此时该题难度为 $18$，出题后 $4$ 个 AI 中的最大权独立集问题的难度分别为 $*,*,*,*$。

所以 $4$ 道题的难度之和为 $10+13+11+18=52$。

【样例解释 2】

一种最优的出题方案如下：

1. 出第 $3$ 个 AI 中的最大权独立集问题，此时该题难度为 $5$，出题后 $4$ 个 AI 中的最大权独立集问题的难度分别为 $1,3,*,5$。

2. 出第 $4$ 个 AI 中的最大权独立集问题，此时该题难度为 $5$，出题后 $4$ 个 AI 中的最大权独立集问题的难度分别为 $1,8,*,*$。

3. 出第 $2$ 个 AI 中的最大权独立集问题，此时该题难度为 $8$，出题后 $4$ 个 AI 中的最大权独立集问题的难度分别为 $9,*,*,*$。

4. 出第 $1$ 个 AI 中的最大权独立集问题，此时该题难度为 $9$，出题后 $4$ 个 AI 中的最大权独立集问题的难度分别为 $*,*,*,*$。

所以 $4$ 道题的难度之和为 $5+5+8+9=27$。

【数据范围】

保证 $\left|d_i\right| \le 10^9$，$1 \le c_i \lt i$，$1\le n \le 400$。

本题采用捆绑测试。

对于编号为奇数的子任务，保证 $d_i \ge 0$。

子任务 $1,2$（$11 \times 2 = 22$ 分）： $n \le 9$。

子任务 $3,4$（$10 \times 2 = 20$ 分）： $n \le 19$。

子任务 $5,6$（$7 \times 2 = 14$ 分）： $n \le 50$，$c_i = i-1$。

子任务 $7,8$（$10 \times 2 = 20$ 分）： $c_i=i-1$。

子任务 $9,10$（$5 \times 2 = 10$ 分）： $n \le 50$。

子任务 $11,12$（$7 \times 2 = 14$ 分）： 无特殊限制。

后记

听说 E.Space 的最大权独立集问题的难度是取了对数的？

听说 E.Space 要把这 $n$ 道题结合成一道题出出来？

听说 E.Space 不会把这些题出在训练里面？