Description

There're $N$ items numbered from $1\ldots N$, each item $i$ with a weight $w_i$ and a value $v_i$. The knapsack's capacity is $W$.

Some items could be selected only after a specific item have been put into the knapsack, or in other words, some items depend on others.

• $d_i = j$ $(i>j>0)$ means item $i$ depends on item $j$, you cannot choose item $i$ until you put item $j$ into the knapsack.
• $d_i = 0$ $(i>0)$ means item $i$ does not depends on any other items.

It's guaranteed that each item depends on no more than one item. All the dependency relationships are vaild, no loop.

Maximize the sum of the values of the items in the knapsack so that the sum of the weights is no more than the knapsack's capacity.

Input

$N\ \ W$
$d_{\large 1\dots N}$
$w_{\large 1\dots N}$
$v_{\large 1\dots N}$

Output

A single integer, represents your answer.

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

0

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

6

10 6
0 1 1 1 2 3 4 5 6 7
1 1 2 2 3 1 2 2 3 1
0 1 1 1 1 1 1 1 1 1

3

13 3
0 1 1 1 3 3 0 0 8 9 10 8 10
1 1 1 1 1 1 1 1 1 1 1 1 1
2 16 32 512 2048 4096 4 1 8 64 1024 128 256

4130

13 25
0 1 1 1 3 3 0 0 8 9 10 8 10
5 6 4 3 7 5 4 7 3 6 5 6 6
0 2 1 2 3 3 3 0 1 2 4 3 2

10

Limits And Hints

$1\le N×W\le 6×10^7,$ $1\le N\le 5×10^4,$ $0\le W\le 6×10^4;$

$1\le w_i\le 200;$

$0\le v_i\le 5000$.