JOI 国有 $N$ 个城市，城市编号为 $1$ 到 $N$。这些城市之间有 $N-1$ 条道路，编号为 $1$ 到 $N-1$。道路 $i$（$1 \le i \le N-1$）双向连接城市 $P_i$（$P_i \le i$）与城市 $i+1$。保证从城市 $1$ 出发，通过若干条道路可以到达任意一个城市。

此外，JOI 国中有 $N-1$ 条与道路平行的河流，编号为 $1$ 到 $N-1$。河流 $i$（$1 \le i \le N-1$）与道路 $i$ 平行，水流方向为从城市 $P_i$ 流向城市 $i+1$。

每个城市各放置一盏灯。每盏灯有一个强度。若城市 $t$（$1 \le t \le N$）中的灯的强度为 $l$，则从该城市出发，通过少于 $l$ 条道路可以到达的城市，都会被这盏灯照亮。

初始时，所有灯的强度均为 $0$，没有任何城市被照亮。

你可以进行任意多次（可以为 $0$ 次）川下り。每次川下り从城市 $1$ 开始，首先将城市 $1$ 的灯的强度增加 $1$。然后重复执行以下操作：

1. 决定是否结束本次川下り。但如果当前所在城市没有流出的河流，则必须结束。
2. 若继续川下り，则选择一条从当前城市流出的河流，沿着水流方向移动到下一个城市，并将到达城市的灯的强度增加 $1$。

如果在城市 $t$ 结束一次川下り，则本次川下り的代价为 $C_t$。

你希望通过进行若干次川下り，使得所有城市最终都被某一盏灯照亮。在此基础上，需要使川下り所产生的总代价最小。

给定道路与代价的信息，请编写程序，求使所有城市都被至少一盏灯照亮所需的川下り总代价的最小值。

输入格式

输入从标准输入给出，格式如下：

$N$

$P_1\ P_2\ \cdots\ P_{N-1}$

$C_1\ C_2\ \cdots\ C_N$

输出格式

输出到标准输出一行，表示使所有城市都被至少一盏灯照亮所需的川下り总代价的最小值。

限制

• $2 \le N \le 700$。
• $1 \le P_i \le i$（$1 \le i \le N-1$）。
• $1 \le C_t \le 10^9$（$1 \le t \le N$）。
• 输入中的所有值均为整数。

子任务

1. （13 分）$N \le 8$。
2. （25 分）$N \le 100$。
3. （7 分）$P_i = 1$（$1 \le i \le N-1$）。
4. （11 分）$P_i = i$（$1 \le i \le N-1$）。
5. （16 分）对于所有 $i$（$1 \le i \le N$），满足 $P_j = i$ 的 $j$（$1 \le j \le N-1$）不超过 $2$ 个。
6. （28 分）无额外限制。

样例数据

输入样例 1

5
1 2 2 4
10 4 8 9 5

输出样例 1

9

第一次川下り选择河流 $1$，在城市 $2$ 结束。此时城市 $1,2$ 的灯的强度各增加 $1$，代价为 $4$。第二次川下り选择河流 $1,3,4$，在城市 $5$ 结束。此时城市 $1,2,4,5$ 的灯的强度各增加 $1$，代价为 $5$。

操作结束后，城市 $1,2$ 的灯强度为 $2$，城市 $3$ 的灯强度为 $0$，城市 $4,5$ 的灯强度为 $1$。城市 $1,2,3,4$ 被城市 $2$ 中强度为 $2$ 的灯照亮，城市 $5$ 被城市 $5$ 中强度为 $1$ 的灯照亮。因此所有城市均被照亮。

总代价为 $4 + 5 = 9$。无法以小于 $9$ 的代价满足条件，因此输出 $9$。

该输入样例满足子任务 $1,2,5,6$ 的限制。

输入样例 2

9
1 1 1 2 5 5 5 3
100 70 80 90 60 30 40 50 30

输出样例 2

90

进行两次经过河流 $1,4,5$ 并在城市 $6$ 结束的川下り，以及一次经过河流 $2,8$ 并在城市 $9$ 结束的川下り。操作结束后，城市 $1$ 的灯强度为 $3$，城市 $2,5,6$ 的灯强度为 $2$，城市 $3,9$ 的灯强度为 $1$，城市 $4,7,8$ 的灯强度为 $0$。

此时所有城市均被至少一盏灯照亮。总代价为 $30 \times 2 + 30 = 90$。无法以小于 $90$ 的代价满足条件，因此输出 $90$。

该输入样例满足子任务 $2,6$ 的限制。