230430稠州PK赛

P4. 点菜

描述

又到了炫饭的时候了，有 N N个菜品，编号分别为 1......N1\ldots N。菜 i i 的价钱为wi w_i，美味程度为 viv_i。

这个饭店比较没法，有些菜必须要先点某些菜才能点。我们用Di=j(i>j>0)表示：如果要选取菜品 i i，就必须先选取菜品 j j。另外，我们用Di=0(i>0)表示：该菜品不依赖于任何菜品。保证每个菜品最多只依赖一个菜品。保证依赖关系合理，不会出现环。

由于经费有限，一共就带了W块钱，请问如何点菜，让美味程度最高

输入

N W

d1......N

w1......N

v1.......N

输出

一个整数，表示答案

样例

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

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

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

提示

1<NxW<6x10^7

1<=N<=5x10^4

0<=W<=6x10^4

子任务组	分值	N=	W\le	特性	依赖的子任务
1	1	21	25	森林，全是树根
2	2	22	26	一棵树
3	3	23	27	菊花
4	4	24	28	森林	2
5	5	100	120	一棵树	1, 3, 4
6	10	200	250	森林，v_i=1	5
7	10		200	森林，w_i=1	5
8	10		250	森林	6, 7
9	15	400	500	森林	8
10	20	7500	8000	森林	9
11	10	50000	1200		10
12	10	1000	60000		10

提交

题目参数

时间限制	1 秒
内存限制	512 MB