A7347 | $三角洲行动Ⅱ（force）$

时间限制1s

内存限制512MB

通过 / 提交0/0

题目描述

三角洲是一款多平台跨端第一人称特战干员战术射击游戏，现在各个年龄段都非常流行，明金也是其中玩家之一。 游戏的商店系统内有 $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$ 个物品的售价、战斗力、所装备上的武器或配件编号。

输出仅一个数字，为最大总战斗力。

输入 #1

输出 #1

C++ 编辑器

输入

输出