题目描述
“工欲善其事,必先利其器”,Mini进入洞口前自然要先来到镇里的装备店买些装备。买每件装备都需要付出一定的体力点,同时也会获得一定的能力点(每种装备都可以买无限次^_^,但人的体力点可是有限的哦^_^)。这些装备还有一种很神奇的力量:当同种装备挑选的数量>=5时,这种装备将产生共鸣,产生更强大的力量,即除了挑选这些物品所获得的能力点之外还会获得额外的Q*K(K表示挑选的数量)点的能力点。但是,同样的,Mini也会付出更多的体力点,即体力点还将多付出Q*K(K表示挑选的数量)点。挑选的物品越多,产生的力量就越大,体力点也会付出越多。不过,这额外获得的能力点、付出的体力点是可以不要的。为了能获得最大的能力点,同时也不至于使自己过分劳累(体力恰好为0不算过分劳累),Mini应该如何购买装备呢?
输入格式
第一行,两个数N和M,N表示有多少种装备,0<=N<=330,每种装备可以买无限次。M表示Mini所拥有的体力点数,0<=M<=400。
以下N行,第I行三个数, WI,QI,Q。WI表示买第I个装备所付出的体力点,QI表示买第I个装备能获得的能力点,Q表示当第I个装备的数量>=5时所产生的共鸣点。0<=WI<=9000,0<=QI<=9000,0<=Q<=9000。
输出格式
一个数,表示在保证Mini不会过分劳累的情况下所能买到的最大能力点
样例输入
样例输出