说明

滑雪者米娅在一个不寻常的滑雪场度过了一天。滑雪场由 $n$ 个滑雪后休息点（以下简称“休息点”）组成，它们由雪道连接，形成一棵以 $1$ 号休息点为根的有根树。每条雪道从编号较小的休息点指向编号较大的休息点。

这棵树定义如下：对于每个 $i > 1$ 的休息点，已知从哪个休息点 $p_i$（$p_i < i$）可以到达它，即它在树中的父节点已知。这唯一确定了所有的雪道（第 $i$ 条雪道通向编号为 $i$ 的休息点）。

白天，米娅每条雪道恰好滑过一次，并记住了每条雪道的乐趣系数 $z_i$ 和速度 $b_i$。

一天结束时，米娅想再滑一次。由于滑了一整天非常疲惫，她会选择一条由 最多 $k$ 条 连续 雪道组成的滑行路线。该路线必须沿着雪道的方向（从编号较小的休息点向编号较大的休息点滑行）。滑完路线后，直升机会接她回家。

对于任意选择的路线，其 紧张度 定义如下。设：

• $z_{\text{first}}$ 为路线上第一条雪道的乐趣系数；
• $z_{\text{last}}$ 为路线上最后一条雪道的乐趣系数；
• $b_i$ 为该路线上所有雪道的速度。

则该路线的紧张度为：

$$z_{\text{last}} \cdot \left(z_{\text{last}} + \sum b_i\right) + z_{\text{first}}^2.$$

当 $k = 1$ 时，公式保持不变，此时 $\text{first} = \text{last}$。

你的任务是确定米娅能滑出的路线的最大紧张度。

输入格式

第一行包含自然数 $n, k$（$1 \le k \le n \le 3 \cdot 10^5$），含义如题目描述所述。

第二行包含 $n-1$ 个整数，其中第 $i$ 个数表示从哪个休息点可以到达编号为 $i+1$ 的休息点（$1 \le p_i \le i$）。

第三行包含 $n-1$ 个整数，其中第 $i$ 个数表示第 $i+1$ 条雪道的乐趣系数（$1 \le z_i \le 10^5$）。

第四行包含 $n-1$ 个整数，其中第 $i$ 个数表示第 $i+1$ 条雪道的速度（$-10^5 \le b_i \le 10^5$）。

输出格式

输出一行一个整数，表示米娅能滑出的路线的最大紧张度。

5 1
1 2 2 1
5 4 8 7
6 3 9 3

200

9 2
1 2 1 1 4 3 6 5
1 3 7 8 4 1 8 2
1 -7 -1 -6 3 8 -1 6

120

提示

第一个样例的解释：由于 $k = 1$，最大紧张度等于各条雪道紧张度的最大值。各条雪道的紧张度分别为 $80, 44, 200$ 和 $119$，最大紧张度为 $200$。

计分方式

子任务	分值	约束条件
1	14	$n \le 1000$
2	23	对于所有 $1 \le i < n$，满足 $z_i = 1$ 且 $b_i > 1$。
3	35	$n \le 50000$
4	38	无额外限制。

翻译由 DeepSeek V3.2 完成