题目描述

手头有 $N$ 个应用，应用 $i$ 占用 $W_i$ 的磁盘空间，价值为 $V_i$。要从磁盘容量为 $M$ 的计算机中选择若干应用安装，使总价值最大。

应用之间存在依赖关系：应用 $i$ 必须在安装了应用 $j$（包括 $j$ 的直接或间接依赖）后才能正常工作（$i$ 依赖 $j$）。每个应用最多依赖一个其他应用。不能正常工作的应用价值为 $0$。

已知依赖关系：应用 $i$ 依赖 $D_i$。请设计安装方案使总价值最大。每个应用只能安装一次，$D_i=0$ 表示无依赖，只要安装就能正常工作。

输入格式

第 $1$ 行：$N, M(0\leq N\leq 100, 0\leq M\leq 500)$

第 $2$ 行：$W_1, W_2, \ldots, W_n(0\leq W_i\leq M)$

第 $3$ 行：$V_1, V_2, \ldots, V_n(0\leq V_i\leq 1000)$

第 $4$ 行：$D_1, D_2, \ldots, D_n(0\leq D_i\leq N, D_i \neq i)$

输出格式

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

样例

3 10
5 5 6
2 3 4
0 1 1

5