在广袤的北方，有 $N$ 座城市，编号从 $1$ 到 $N$。城市 $i$ 中居住着 $A_i$ 位市民。共有 $N-1$ 条道路，编号从 $2$ 到 $N$。道路 $j$ 连接城市 $j$ 和城市 $P_j$，其中 $P_j < j$。任何城市连接的道路数量最多为 $36$ 条。

冬季期间，由于危险的驾驶条件，所有道路都将转换为单向高速公路。也就是说，道路 $j$ 将变成一条从城市 $j$ 到城市 $P_j$ 的单向高速公路，或者从城市 $P_j$ 到城市 $j$ 的单向高速公路。

每位市民都想给其他所有市民寄送一张节日贺卡。如果市民 $x$ 居住的城市可以通过高速公路到达市民 $y$ 居住的城市，那么市民 $x$ 就可以给市民 $y$ 寄送一张贺卡。

在将所有道路转换为高速公路后，最多可以寄送多少张节日贺卡？

输入格式

第一行包含一个整数 $N$ ($2 \le N \le 200\,000$)。

第二行包含 $N$ 个整数 $A_1, \dots, A_N$ ($1 \le A_i \le 10\,000$)。

第三行包含 $N-1$ 个整数 $P_2, \dots, P_N$ ($1 \le P_j < j$)。

设 $D$ 为任何城市连接的道路数量的最大值。保证 $D \le 36$。

子任务

• 对于 $25$ 分中的 $5$ 分，$N \le 10$。
• 对于另外 $5$ 分，$N \le 1\,000$ 且 $D \le 10$。
• 对于另外 $5$ 分，$D \le 18$。
• 对于另外 $5$ 分，共有 $37$ 座城市，其中一座城市与另外 $36$ 座城市相连，而这 $36$ 座城市仅与这一座城市相连。

输出格式

输出一行，包含一个整数，表示将所有道路转换为高速公路后，最多可以寄送的贺卡总数。

样例

输入 1

4
3 3 4 1
1 2 1

输出 1

67

说明

一种可能的转换方式是：道路 $2$ 变为从城市 $2$ 到城市 $1$ 的单向公路，道路 $3$ 变为从城市 $3$ 到城市 $2$ 的单向公路，道路 $4$ 变为从城市 $1$ 到城市 $4$ 的单向公路。

初始道路及城市人口（括号内）

转换后的高速公路情况如下：

转换后的高速公路

城市 $3$ 的每位市民可以向城市 $3$ 的市民寄送 $3$ 张贺卡，向城市 $2$ 的市民寄送 $3$ 张贺卡，向城市 $1$ 的市民寄送 $3$ 张贺卡，向城市 $4$ 的市民寄送 $1$ 张贺卡，城市 $3$ 总共寄出 $40$ 张贺卡。

同样地： 城市 $2$ 的市民每人寄出 $6$ 张贺卡，总计 $18$ 张。 城市 $1$ 的市民每人寄出 $3$ 张贺卡，总计 $9$ 张。 * 城市 $4$ 的市民无法寄出任何贺卡。

总计寄出 $40 + 18 + 9 = 67$ 张贺卡。