A7347. 三角洲行动Ⅱ（force）
编程题
普及+/提高
知识点
题目描述
三角洲是一款多平台跨端第一人称特战干员战术射击游戏，现在各个年龄段都非常流行，明金也是其中玩家之一。
游戏的商店系统内有 $n$ 种武器及配件，用 $1 \sim n$ 编号，每个物品都最多购买一次。其中配件是需要装备在某个指定的武器或者某个指定的其他配件上才会发挥作用。
对于第 $i$ 个物品，它在商店系统内售价 $v_i$ 元，如果 $s_i=0$ 则表示这个物品是武器，武器本身会提供 $b_i$ 的战斗力；如果 $s_i \ne 0$，它是一种配件，它所装备上的武器或配件编号为 $s_i$，增加 $b_i$ 的战斗力。
明金有游戏币 $m$ 元，他想要知道，在花费不超过 $m$ 元的情况下，通过购买武器及相关配件，可以获得的最大战斗力。
游戏的商店系统内有 $n$ 种武器及配件，用 $1 \sim n$ 编号，每个物品都最多购买一次。其中配件是需要装备在某个指定的武器或者某个指定的其他配件上才会发挥作用。
对于第 $i$ 个物品，它在商店系统内售价 $v_i$ 元，如果 $s_i=0$ 则表示这个物品是武器，武器本身会提供 $b_i$ 的战斗力；如果 $s_i \ne 0$，它是一种配件，它所装备上的武器或配件编号为 $s_i$，增加 $b_i$ 的战斗力。
明金有游戏币 $m$ 元，他想要知道，在花费不超过 $m$ 元的情况下，通过购买武器及相关配件，可以获得的最大战斗力。
输入格式
输入的第一行是二个正整数 $n,m$，武器及配件的总数量、明金拥有的金币数量。
接着 $n$ 行，每行三个数字 $v_i,b_i,s_i$，表示第 $i$ 个物品的售价、战斗力、所装备上的武器或配件编号。
接着 $n$ 行，每行三个数字 $v_i,b_i,s_i$，表示第 $i$ 个物品的售价、战斗力、所装备上的武器或配件编号。
输出格式
输出仅一个数字，为最大总战斗力。
输入输出样例
输入 #1
8 12 6 10 0 8 5 1 3 2 0 1 8 1 1 3 3 3 1 2 2 7 3 3 9 0
输出 #1
27
说明/提示
### 样例 1 解释
共有 $8$ 件物品，明金有 $12$ 元，物品信息如下表。
| 物品编号 | 售价 | 战斗力 | 主件编号 |
| ---- | -- | --- | ---- |
| 1 | 6 | 10 | 无 |
| 2 | 8 | 5 | 1 |
| 3 | 3 | 2 | 无 |
| 4 | 1 | 8 | 1 |
| 5 | 1 | 3 | 3 |
| 6 | 3 | 1 | 2 |
| 7 | 2 | 7 | 3 |
| 8 | 3 | 9 | 无 |
最优方案为购买物品 $1$ 及其附件 $4$，再单独购买物品 $8$。花费 $6+1+3=10$ 元，获得战斗力 $10+8+9=27$。
### 附件
更多样例请查看：[force test.zip](https://pms-wscdn.xmwol.com/file/825842ca3c6b7840.zip)
### 数据范围
对于所有测试数据有：
$$ 1 \le n \le 100 $$
$$ 1 \le v_i \le m \le 10^9 $$
$$ 1 \le b_i \le 10 $$
$$ 0 \le s_i \le i $$
| 测试点 | $n \le$ | $m \le$ | 特殊性质 |
| ----- | ------- | ------- | ----------------------------- |
| 1~2 | 10 | $10^2$ | 无 |
| 3~5 | 15 | $10^9$ | 无 |
| 6~9 | 50 | 50 | 无 |
| 10~12 | 50 | $10^4$ | 保证每个武器最多有 $2$ 个配件且任何配件不会有它的配件 |
| 13~14 | 50 | $10^9$ | 无 |
| 15 | 100 | 100 | $s_i=i-1$ |
| 16~17 | 100 | 100 | 无 |
| 18~20 | 100 | $10^9$ | 无 |
共有 $8$ 件物品，明金有 $12$ 元，物品信息如下表。
| 物品编号 | 售价 | 战斗力 | 主件编号 |
| ---- | -- | --- | ---- |
| 1 | 6 | 10 | 无 |
| 2 | 8 | 5 | 1 |
| 3 | 3 | 2 | 无 |
| 4 | 1 | 8 | 1 |
| 5 | 1 | 3 | 3 |
| 6 | 3 | 1 | 2 |
| 7 | 2 | 7 | 3 |
| 8 | 3 | 9 | 无 |
最优方案为购买物品 $1$ 及其附件 $4$，再单独购买物品 $8$。花费 $6+1+3=10$ 元，获得战斗力 $10+8+9=27$。
### 附件
更多样例请查看：[force test.zip](https://pms-wscdn.xmwol.com/file/825842ca3c6b7840.zip)
### 数据范围
对于所有测试数据有：
$$ 1 \le n \le 100 $$
$$ 1 \le v_i \le m \le 10^9 $$
$$ 1 \le b_i \le 10 $$
$$ 0 \le s_i \le i $$
| 测试点 | $n \le$ | $m \le$ | 特殊性质 |
| ----- | ------- | ------- | ----------------------------- |
| 1~2 | 10 | $10^2$ | 无 |
| 3~5 | 15 | $10^9$ | 无 |
| 6~9 | 50 | 50 | 无 |
| 10~12 | 50 | $10^4$ | 保证每个武器最多有 $2$ 个配件且任何配件不会有它的配件 |
| 13~14 | 50 | $10^9$ | 无 |
| 15 | 100 | 100 | $s_i=i-1$ |
| 16~17 | 100 | 100 | 无 |
| 18~20 | 100 | $10^9$ | 无 |