三角洲是一款多平台跨端第一人称特战干员战术射击游戏，现在各个年龄段都非常流行，明金也是其中玩家之一。

游戏的商店系统内有n种武器及配件，用1~n编号，每个物品都最多购买一次。其中配件是需要装备在某个指定的武器或者某个指定的其他配件上才会发挥作用。

对于第$i$个物品，它在商店系统内售价$v_i$元，如果$s_i$ 则表示这个物品是武器，武器本身会提供$b_i$的战斗力；如果$s_i\neq0$，它是一种配件，它所装备上的武器或配件编号为$s_i,$ 增加$b_i$的战斗力。

       明金有游戏币$m$元，他想要知道，在花费不超过$m$元的情况下，通过购买武器及相关配件，可以获得的最大战斗力。

从文件force.in中读入数据。

输入的第一行是二个正整数n、m，武器及配件的总数量、明金拥有的金币数量。

接着n行，每行三个数字$v_i,b_i,s_i$，表示第i个物品的售价、战斗力、所装备上的武器或配件编号。

输出到文件force.out中。

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

共有8件物品，明金有12元，物品信息如下表。

    最优方案为购买物品1及其附件4，再单独购买物品8。花费6+1+3=10元，获得战斗力10+8+9=27。