题目描述

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

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

但是和之前不一样，这回他想把 $n$ 道题整合成一道题出出来。

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

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

有些 AI 之间可以互相通信，对于所有的 $2 \le i \le n$ ，第 $i$ 个 AI 可以和第 $c_i$ 个 AI 互相通信。其中 $c_i<i$。所以，这些 AI 连成了一个树的形状。此外，其他对 AI 不可以互相通信。

小 E 每次可以选择一个存有一道最大权独立集问题的 AI，结合它能够直接互相通信的所有 AI 中的问题，变成一道新的最大权独立集问题。整合问题时总有难度损失，不可能是把所有问题的难度直接相加。这道新的最大权独立集问题的难度是那些能够直接互相通信的 AI 中的题目难度和减去原本存在该 AI 上的问题的难度。然后那些能够直接互相通信的 AI 中的问题难度会变成 $0$。

小 E 希望通过若干次操作，把 $n-1$ 个 AI 中的题目难度都变成 $0$，然后把最后一个 AI 中的题目出出来。

由于出题人的丧病心理，小 E 想要出出来的最大权独立集问题的难度尽量大。

他想叫你帮他解决这个问题，还说如果你成功解决了这个问题，那么在出那道最大权独立集问题的时候，他会帮你提交一份标程代码。

输入格式

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

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

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

输出格式

一行一个整数表示答案。

4
-1 2 3 4
1 1 1

10

提示

保证 $1\le n\le 351493$。

保证 $1\le c_i <i$。

保证 $|d_i|\le 10^9$。

子任务 1（13 分）：$c_i=i-1$。

子任务 2（6 分）：$d_i>0$。

子任务 3（11 分）：$n\le 7$。

子任务 4（13 分）：$n\le 16$。

子任务 5（22 分）：$n\le 100$。

子任务 6（35 分）：无特殊性质。