小明的背包6 ### 题目描述 小明有一个容量为 $V$ 的背包。 这天他去商场购物，商场一共有 $N$ 件物品，第 $i$ 件物品的体积为 $w_i$，价值为 $v_i$。 物品和物品之间存在依赖关系$(i,j)$，其含义为只有购买了 $i$ 物品才能购买 $j$ 物品。 小明想知道在购买的物品总体积不超过 $V$ 的情况下所能获得的最大价值为多少，请你帮他算算。 ### 输入描述 输入第 $1$ 行包含两个整数 $N,V$，表示商场物品的数量和小明的背包容量。 第 $2\sim N+1$ 行包含 $3$ 个正整数 $w,v,s$，表示物品的体积和价值以及依赖关系：即第 $i$ 件物品依赖于第 $s$ 件物品。（若 $s_i=0$，则表示第 $i$ 件物品不依赖于任何物品） $1\leq N,V\leq10^2$，$1 \leq w_i,v_i \leq10^2$，$1\leq s_i \leq n$。 ### 输出描述 输出一行整数表示小明所能获得的最大价值。 ### 输入输出样例 #### 示例 1 >输入 ```txt 6 15 3 4 0 2 3 1 2 5 1 3 5 1 4 8 2 3 9 2 ``` >输出 ```txt 29 ```