小明最近在玩一个游戏,游戏中很重要的一个部分就是买装备。在这个游戏中,买装备的规则是这样的:游戏中一共有n件装备装备需要用金币购买,除了一件初始装备外,每件装备都有唯一的前置装备,而要买某一件装备,必须要先买它的前置装备。每件装备都有一个价格,和一个能力值。现在,小明拥有m个金币,他想尽可能地多获得能力值,请你帮忙求出,在花费不超过m个金币的情况下购买的装备,能获得的能力值总和的最大值。数据满足n<=200, m<=500.装备的价格和能力值均为不超过200的正整数。
输入的第一行包含两个整数,代表题目描述中的n和m,接下来n行,每行3个整数,用空格隔开,分别代表第i件装备的前置装备的编号,第i件装备的价格,以及第i件装备的能力值。装备编号从0开始。前置装备为-1时,代表该装备为初始装备,没有前置装备。初始装备有且仅有1个。输入保证装备没有循环依赖。
输出一个整数,代表能获得的最大能力值。
请输入正确的证书编号
学员姓名:孙兴民
课程:Scratch Level 1
发证日期:2019.08.15