地方选举临近了！

在权力更迭之前，需要给市政厅的一个部门发放奖金。我们可以用一棵树来表示该部门的层级结构，其中节点 1 为主管，每个员工的直接上司是其在树中的父节点。

如果第 $i$ 名员工获得的奖金至少为 $c_i$，那么他在下一年的生产力将增加 $p_i$，否则生产力保持不变。并不要求所有员工都获得奖金，但对于每一位获得奖金的员工，其直接上司也必须获得至少一定的正数奖金（即使金额为 1）。

在奖金总预算不超过 $K$ 的前提下，确定部门生产力增加值的最大可能值。

输入格式

第一行包含自然数 $N$ 和 $K$。

第二行包含 $N-1$ 个整数 $s_i$ ($1 \le s_i \le i$)，其中第 $i$ 个数表示第 $i+1$ 名员工的直接上司。

第三行包含 $N$ 个整数 $p_1, p_2, \dots, p_N$。

第四行包含 $N$ 个整数 $c_1, c_2, \dots, c_N$。

输出格式

在唯一的一行中输出在给定预算下生产力增加值的最大可能值。

子任务

在所有子任务中，满足 $2 \le N \le 5\,000$ 且 $1 \le K \le 5\,000$。

对于所有 $i = 1, \dots, N$，满足 $1 \le p_i \le 10^5$ 且 $1 \le c_i \le 5\,000$。

样例

输入 1

2 100
1
10 10
101 100

输出 1

0

输入 2

5 7
1 1 2 2
2 1 2 3 3
4 2 4 2 3

输出 2

6

输入 3

4 9
1 2 2
3 4 4 2
2 5 5 4

输出 3

7

说明

第二个样例的解释： 一个有效的奖金分配方案如下：员工依次获得的奖金为 1, 1, 0, 2 和 3。 分配方案 1, 1, 1, 2, 3 是无效的，因为奖金总额超过了允许的预算。 分配方案 0, 1, 1, 2, 3 也是无效的，因为员工 2 获得了奖金，但其直接上司没有获得奖金。