当前没有测试数据。

4.软件安装

题目描述

现在我们的手头有$N$个软件，对于一个软件$i$，它要占用$W_i$的磁盘空间，它的价值为$V_i$。我们希望从中选择一些软件安装到一台磁盘容量为$M$计算机上，使得这些软件的价值尽可能大（即$V_i$的和最大）。

但是现在有个问题：软件之间存在依赖关系，即软件$i$只有在安装了软件$j$（包括软件$j$的直接或间接依赖）的情况下才能正确工作（软件$i$依赖软件$j$）。幸运的是，一个软件最多依赖另外一个软件。如果一个软件不能正常工作，那么它能够发挥的作用为$0$。

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

输入格式

• 第$1$行：$N$，$M$
• 第$2$行：$W_1$，$W_2$，$\cdots$，$W_n$
• 第$3$行：$V_1$，$V_2$，$\cdots$，$V_n$
• 第$4$行：$D_1$，$D_2$，$\cdots$，$D_n$

输出格式

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

数据范围与提示

对于$100\%$的数据：

• $0 \leq N \leq 100$
• $0 \leq M \leq 500$
• $0 \leq W_i \leq M$
• $0 \leq V_i \leq 1000$
• $0 \leq D_i \leq N$，且$D_i \neq i$

样例

3 10
5 5 6
2 3 4
0 1 1

5