Có ~N~ món đồ được đánh số từ ~1 \ldots N~, mỗi món đồ ~i~ có khối lượng ~w_i~ và giá trị ~v_i~. Sức chứa của chiếc ba lô là ~W~.

Một số món đó chỉ có thể được chọn sau khi một món đồ cụ thể đã được cho vào ba lô, hay nói cách khác, một số món đồ phụ thuộc vào những món đồ khác.

• ~d_i = j (i>j>0)~ có nghĩa là món đồ ~i~ phụ thuộc vào món đồ ~j~, bạn không thể chọn món ~i~ cho đến khi bạn đặt món ~j~ vào ba lô.
• ~d_i = 0 (i>0)~ có nghĩa là món đồ ~i~ không phụ thuộc vào bất kỳ mục nào khác. Đảm bảo rằng mỗi mục phụ thuộc vào không nhiều hơn một mục. Tất cả các mối quan hệ phụ thuộc đều có giá trị, không có vòng lặp.

Hãy tối đa hóa tổng giá trị của các món đồ trong ba lô sao cho tổng các khối số không vượt quá sức chứa của ba lô.

Input

• Dòng đầu tiên là 2 số ~N~ và ~W~
• Dòng thứ 2 là dãy ~d_1 \ldots d_N~
• Dòng thứ 2 là dãy ~w_1 \ldots w_N~
• Dòng thứ 2 là dãy ~v_1 \ldots v_N~

Output

Một số nguyên duy nhất là kết quả của bài toán

Sample

Input #1

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

Output #1

0

Input #2

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

Output #2

6

Input #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

Output #3

4130

Giới hạn

• ~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~.