软件安装

题目描述

有 $N$ 个软件。软件 $i$ 占用 $W_i$ 的磁盘空间，能够产生价值 $V_i$。请选择若干软件安装到容量为 $M$ 的磁盘中，使能够正常工作的已安装软件价值之和最大。

软件之间可能存在依赖关系。软件 $i$ 只有在其依赖的软件及所有间接依赖都已安装时才能正常工作。每个软件至多直接依赖一个软件，$D_i$ 表示软件 $i$ 直接依赖的软件编号；若 $D_i=0$，则软件 $i$ 没有依赖。不能正常工作的已安装软件价值为 $0$。

每个软件最多安装一次。

输入格式

第一行包含两个整数 $N,M$。

第二行包含 $N$ 个整数 $W_1,W_2,\ldots,W_N$。

第三行包含 $N$ 个整数 $V_1,V_2,\ldots,V_N$。

第四行包含 $N$ 个整数 $D_1,D_2,\ldots,D_N$。

输出格式

输出一个整数，表示能够获得的最大价值。

样例输入 1

3 10
5 5 6
2 3 4
0 1 1

样例输出 1

5

数据范围

$0\le N\le 100$，$0\le M\le 500$，$0\le W_i\le M$，$0\le V_i\le 1000$，$0\le D_i\le N$，且 $D_i\ne i$。