You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时空限制

1S/512M

题目描述

apiadu 正在对公司的组织架构进行调整以提升效率。

公司共有 $n$ 个职位，编号为 $1 \sim n$。其中 $1$ 号职位是最高职位。对于 $i \ge 2$ 的职位，其直接上级为 $p_i$（保证 $p_i < i$），这就构成了一棵以 $1$ 为根的树形结构。 下属职位的定义为：一个职位的直接下属，以及其直接下属的所有下属。

目前，第 $i$ 号职位上的员工拥有能力值 $a_i$。此外，还有 $m$ 名候选人，第 $j$ 名候选人的能力值为 $b_j$。

apiadu 的调整方案如下： 从当前的 $n$ 个职位中选出 $k$ 个职位（下标设为 $x_1 < x_2 < \dots < x_k$），并从 $m$ 名候选人中选出 $k$ 人（下标设为 $y_1 < y_2 < \dots < y_k$），其中 $0 \le k \le \min(n, m)$。 然后进行替换：对于每一组 $(x_j, y_j)$，将第 $x_j$ 号职位的员工替换为第 $y_j$ 号候选人（能力值变为 $b_{y_j}$）。

调整完成后，定义第 $i$ 号职位的工作效率 $s_i$ 为：该职位及其所有下属职位上的员工能力值之和。 公司的总工作效率定义为：$\sum_{i=1}^n s_i \times i$。

请帮 apiadu 计算在最优的调整方案下，公司能达到的最大总工作效率。

格式

输入格式

第一行包含两个整数 $n,m$，分别表示职位数量和候选人数量。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示目前每位员工的能力值。

第三行包含 $m$ 个整数 $b_1,b_2,\dots,b_m$，表示每位候选人的能力值。

第四行包含 $n-1$ 个整数 $p_2,p_3,\dots,p_n$，表示 $2 \sim n$ 号职位的直接上级编号。

输出格式

输出一行一个整数，表示调整后公司总工作效率的最大值。

样例

样例输入 #1

3 2
10 20 30
100 5
1 1

样例输出 #1

470

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

对于 $100\%$ 的数据：$1 \le n,m \le 4000$，$1 \le a_i,b_i \le 10^8$，$1 \le p_i <i$。