滑雪爱好者 Mia 在一个不寻常的滑雪胜地度过了一天。该滑雪胜地由 $n$ 个滑雪场（以下简称为 apres）组成，它们通过滑道连接，形成一棵以编号为 $1$ 的 apres 为根的有根树。每条滑道都是有向的，从编号较小的 apres 指向编号较大的 apres。

这棵树的定义如下：对于每个 $i > 1$ 的 apres，已知从哪个 apres $p_i$ ($p_i < i$) 可以到达它，即它在树中的父亲节点是已知的。这唯一确定了所有的滑道（滑道 $i$ 通往编号为 $i$ 的 apres）。

在这一天中， Mia 将每条滑道都恰好滑了一次，并且记下了每条滑道的趣味系数 $z_i$ 和速度 $b_i$。

在一天结束时，Mia 想要再滑一次。由于整天滑雪让她非常疲惫，她将选择一条由最多 $k$ 条连续滑道组成的路线。该路线必须遵循滑道的方向（从编号较小的 apres 到编号较大的 apres）。滑完这条路线后，直升机会接她回家。

对于任意选择的路线，我们定义其狂热度（hecticness）如下。设：

• $z_{\text{first}}$ 为路线中第一条滑道的趣味系数
• $z_{\text{last}}$ 为路线中最后一条滑道的趣味系数
• $b_i$ 为该路线中所有滑道的速度

那么该路线的狂热度为：$z_{\text{last}} \cdot (z_{\text{last}} + \sum b_i) + z_{\text{first}}^2$。在 $k = 1$ 的情况下，公式保持不变，且满足 $\text{first} = \text{last}$。

你的任务是确定 Mia 可以滑行的路线的最大狂热度。

输入格式

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

第二行包含 $n - 1$ 个整数，其中第 $i$ 个数表示可以从哪个 apres 到达编号为 $i + 1$ 的 apres ($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$)。

输出格式

在第一行也是唯一一行中，输出一个整数——Mia 可以滑行的路线的最大狂热度。

子任务

样例

输入样例 1

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

输出样例 1

200

输入样例 2

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

输出样例 2

120

说明

第一个样例的解释：由于 $k = 1$，路线的最大狂热度等于单条滑道的最大狂热度。各条滑道的狂热度分别为 $80, 44, 200$ 和 $119$。最大狂热度为 $200$。