题目描述

现在我们的手头有 NN 个软件,对于一个软件 ii,它要占用 WiW_i 的磁盘空间,它的价值为 ViV_i。我们希望从中选择一些软件安装到一台磁盘容量为 MM 计算机上,使得这些软件的价值尽可能大(即 ViV_i 的和最大)。

但是现在有个问题:软件之间存在依赖关系,即软件 ii 只有在安装了软件 jj(包括软件 jj 的直接或间接依赖)的情况下才能正确工作(软件 ii 依赖软件 jj)。幸运的是,一个软件最多依赖另外一个软件。如果一个软件不能正常工作,那么它能够发挥的作用为 00

我们现在知道了软件之间的依赖关系:软件 ii 依赖软件 DiD_i。现在请你设计出一种方案,安装价值尽量大的软件。一个软件只能被安装一次,如果一个软件没有依赖则 Di=0D_i=0,这时只要这个软件安装了,它就能正常工作。

输入格式

第 1 行:N,M(0N100,0M500)N,M(0\leq N\leq 100, 0\leq M\leq 500)

第 2 行:W1,W2,...Wi,...,Wn(0WiM)W_1,W_2, ... W_i, ..., W_n (0\leq W_i\leq M)

第 3 行:V1,V2,...,Vi,...,Vn(0Vi1000)V_1, V_2, ..., V_i, ..., V_n (0\leq V_i\leq 1000)

第 4 行:$D_1, D_2, ..., D_i, ..., D_n (0\leq D_i\leq N, D_i≠i)$

输出格式

一个整数,代表最大价值。

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

1 comments

  • 1

Information

ID
2427
Time
1000ms
Memory
256MiB
Difficulty
6
Tags
(None)
# Submissions
42
Accepted
14
Uploaded By