Local elections are approaching!
Before the change of government, it is necessary to distribute bonuses in one unnamed department of the city administration. We can represent the administration's hierarchy as a tree where node 1 is designated as the director, and the direct supervisor of each employee is their parent in the tree.
If the $i$-th employee receives a bonus of at least $c_i$, their productivity in the following year will increase by $p_i$, while otherwise it remains unchanged. It is not necessary for all employees to receive a bonus, but for every employee who receives a bonus, it must hold that their direct supervisor has also received at least some positive bonus (even if it is an amount of 1).
Determine the maximum possible increase in the total productivity of the department if the total budget for bonuses is at most $K$.
Input
The first line contains the natural numbers $N$ and $K$.
The second line contains $N-1$ numbers $s_i$ ($1 \le s_i \le i$), where the $i$-th number denotes the direct supervisor of the $(i+1)$-th employee.
The third line contains $N$ numbers $p_1, p_2, \dots, p_N$.
The fourth line contains $N$ numbers $c_1, c_2, \dots, c_N$.
Output
In the only line, print the maximum possible increase in productivity given the specified budget.
Subtasks
In all subtasks, $2 \le N \le 5\,000$ and $1 \le K \le 5\,000$. For all $i = 1, \dots, N$, it holds that $1 \le p_i \le 10^5$ and $1 \le c_i \le 5\,000$.
| Subtask | Points | Constraints |
|---|---|---|
| 1 | 7 | $N \le 20$ |
| 2 | 9 | $c_i = 1$ for all $i$, and additionally, if $j$ is the supervisor of $i$, then $p_j \ge p_i$. |
| 3 | 14 | For all $i < N$, the direct supervisor of $i+1$ is $i$. |
| 4 | 19 | $N, K \le 500$ |
| 5 | 21 | $N \le 100$ |
| 6 | 30 | No additional constraints. |
Examples
Input 1
2 100 1 10 10 101 100
Output 1
0
Input 2
5 7 1 1 2 2 2 1 2 3 3 4 2 4 2 3
Output 2
6
Input 3
4 9 1 2 2 3 4 4 2 2 5 5 4
Output 3
7
Note
Explanation of the second example: An example of a valid bonus distribution is as follows: employees receive 1, 1, 0, 2, and 3 bonuses, respectively. The distribution 1, 1, 1, 2, 3 is not valid because the total number of awarded bonuses exceeds the allowed budget. The distribution 0, 1, 1, 2, 3 is also not valid because employee 2 received a bonus, but their direct supervisor did not.