{"raw_statement":[{"iden":"statement","content":"E.Space 喜欢出最大权独立集问题。\n\n接下来，他还想出 $n$ 道最大权独立集问题。\n\nE.Space 有 $n$ 个 AI，编号为 $1\\sim n$。\n\n开始第 $i$ 个 AI 里面存有一道 E.Space 事先出好的一道难度为 $d_i$ 的最大权独立集问题。\n\n有些 AI 之间可以互相通信，对于所有的 $2 \\le i \\le n$，第 $i$ 个 AI 可以和第 $c_i$ 个 AI 互相通信。此外，其他对 AI 不可以互相通信。\n\nE.Space 每次可以选择一个存有一道最大权独立集问题的 AI，把存在里面的题出出来，然后清除存在这个 AI 里的题。\n\n在 E.Space 出题之后清除题目之前，AI 会把这道题发给能和它通信的所有 AI。\n\n如果一个收到这道题的 AI 中已经存有一道最大权独立集问题，那么这个 AI 会把这个收到的题和原本存有的题结合起来，变成一道新的最大权独立集问题存起来。形式化地，如果这个 AI 原来存了一道难度为 $x$ 的最大权独立集问题，接着收到了一道难度为 $y$ 的最大权独立集问题，那么结合之后是一道难度为 $x+y$ 的最大权独立集问题。\n\n如果一个收到题的 AI 中未存有题，那么这个 AI 会销毁收到的这个信息。\n\n由于出题人的丧病心理，E.Space 想要出出来的 $n$ 道最大权独立集问题的难度之和尽量大。\n\n他想叫你帮他解决这个问题，还说如果你成功在这场训练中解决了这个问题，那么在出那 $n$ 道最大权独立集问题的时候，他会在训练结束前 10 分钟切换至你的账号然后提交一份标程代码。"},{"iden":"input","content":"第一行一个正整数 $n$。\n\n第二行 $n$ 个整数，第 $i$ 个表示 $d_i$。\n\n第三行 $n-1$ 个整数，第 $i$ 个表示 $c_{i+1}$。"},{"iden":"output","content":"一行一个整数，表示最大的难度之和。"},{"iden":"note","content":"### 【样例解释 1】\n\n一种最优的出题方案如下：\n\n1. 出第 $2$ 个 AI 中的最大权独立集问题，此时该题难度为 $10$，出题后 $4$ 个 AI 中的最大权独立集问题的难度分别为 $11,*,13,5$ ($*$ 表示该 AI 中没有最大权独立集问题，下同)。\n\n2. 出第 $3$ 个 AI 中的最大权独立集问题，此时该题难度为 $13$，出题后 $4$ 个 AI 中的最大权独立集问题的难度分别为 $11,*,*,18$。\n\n3. 出第 $1$ 个 AI 中的最大权独立集问题，此时该题难度为 $11$，出题后 $4$ 个 AI 中的最大权独立集问题的难度分别为 $*,*,*,18$。\n\n4. 出第 $4$ 个 AI 中的最大权独立集问题，此时该题难度为 $18$，出题后 $4$ 个 AI 中的最大权独立集问题的难度分别为 $*,*,*,*$。\n\n所以 $4$ 道题的难度之和为 $10+13+11+18=52$。\n\n### 【样例解释 2】\n\n一种最优的出题方案如下：\n\n1. 出第 $3$ 个 AI 中的最大权独立集问题，此时该题难度为 $5$，出题后 $4$ 个 AI 中的最大权独立集问题的难度分别为 $1,3,*,5$。\n\n2. 出第 $4$ 个 AI 中的最大权独立集问题，此时该题难度为 $5$，出题后 $4$ 个 AI 中的最大权独立集问题的难度分别为 $1,8,*,*$。\n\n3. 出第 $2$ 个 AI 中的最大权独立集问题，此时该题难度为 $8$，出题后 $4$ 个 AI 中的最大权独立集问题的难度分别为 $9,*,*,*$。\n\n4. 出第 $1$ 个 AI 中的最大权独立集问题，此时该题难度为 $9$，出题后 $4$ 个 AI 中的最大权独立集问题的难度分别为 $*,*,*,*$。\n\n所以 $4$ 道题的难度之和为 $5+5+8+9=27$。\n\n### 【数据范围】\n\n保证 $\\left|d_i\\right| \\le 10^9$，$1 \\le c_i \\lt i$，$1\\le n \\le 400$。\n\n**本题采用捆绑测试。**\n\n对于编号为奇数的子任务，保证 $d_i \\ge 0$。\n\n子任务 $1,2$（$11 \\times 2 = 22$ 分）：\n$n \\le 9$。\n\n子任务 $3,4$（$10 \\times 2 = 20$ 分）：\n$n \\le 19$。\n\n子任务 $5,6$（$7 \\times 2 = 14$ 分）：\n$n \\le 50$，$c_i = i-1$。\n\n子任务 $7,8$（$10 \\times 2 = 20$ 分）：\n$c_i=i-1$。\n\n子任务 $9,10$（$5 \\times 2 = 10$ 分）：\n$n \\le 50$。\n\n子任务 $11,12$（$7 \\times 2 = 14$ 分）：\n无特殊限制。\n\n### 后记\n\n听说 E.Space 的最大权独立集问题的难度是取了对数的？\n\n听说 E.Space 要把这 $n$ 道题结合成一道题出出来？\n\n听说 E.Space 不会把这些题出在训练里面？\n\n"}],"translated_statement":null,"sample_group":[["4\n1 10 3 5\n1 2 3\n","52\n"],["4\n1 -2 5 5\n1 2 2\n","27\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}