g6-07509. 预算依赖选择 未做

给定一棵以 $1$ 为根的有根树，共 $n$ 个结点。结点 $i$ 有代价 $c_i$ 与收益 $w_i$。总预算为 $B$。

选择若干结点：若选了结点 $i$（$i\ne 1$），必须同时选它的父亲；被选结点的代价之和不能超过 $B$。求收益之和的最大值。

允许一个结点都不选，此时收益之和为 $0$。

第一行两个整数 $n$ 与 $B$。

第二行 $n$ 个整数 $w_1,w_2,\dots ,w_n$。

第三行 $n$ 个整数 $c_1,c_2,\dots ,c_n$。

第四行 $n-1$ 个整数 $f_2,f_3,\dots ,f_n$，其中 $f_i$ 表示结点 $i$ 的父亲，保证 $f_i<i$（$n=1$ 时该行为空）。

一行一个整数，表示收益之和的最大值。

输入：

3 5
10 20 30
2 3 4
1 1

输出：

30

选 $\{1,3\}$：代价 $2+4=6$ 超过预算 $5$，不行；选 $\{1,2\}$：代价 $5$，收益 $30$。

• 对于 $30\%$ 的测试点，$1\le n\le 20$；
• 对于 $60\%$ 的测试点，$1\le n\le 100$；
• 对于全部测试点，$1\le n\le 500$，$1\le B\le 200$，$0\le c_i\le 100$，$-10^4\le w_i\le 10^4$。