#描述#
Altynai是一个纯正的DOTA菜鸟..而且他玩DOTA有一个特点,就是特别喜欢那些DPS(每秒输出的伤害)高的英雄..<br />
而且买的装备也是专门买那种加攻击力加的很多的装备.. = = <br />
现在他又在玩DOTA了..由于一开始杀了很多次敌方的英雄和小兵,Altynai现在身上有一些小钱了..<br />
现在他开心的回自己的基地准备买装备了..由于有限制,他身上最多能带6个装备,而且每种装备他最多买一件..<br />
由于时间紧迫,他必须抓紧时间来买装备,从而能使自己的攻击力增加的最多..当然了,Altynai不在意花了多少钱..<br />
毕竟他最在意的是能增加的攻击力!<br />
请你帮帮Altynai,算一下他能增加的最大的攻击力.<br />

#格式#
##输入格式##
有多组数据,每组数据第一行为2个整数N和T(1&lt=N&lt=15,0&lt=T&lt=100000),表示基地装备的种类和Altynai现在身上有的钱。
接下去N行,每行有1个字符串s(1&lt=s长度&lt=20,只含有小写字母)和2个整数d和m(0&lt=d&lt=250,100&lt=m&lt=6000),分别表示每种武器的名字,增加的攻击力和价格。

##输出格式##
算一下他能增加的最大的攻击力.

#样例1#
##样例输入1##

6 100000
shengjian 250 6200
duijian 100 4450
yangdao 150 6666
budaofu 200 3000
hudie 180 4100
anmie 200 3500

##样例输出1##

1080

#限制#
1000ms
32768KB

#提示#

#来源#
1.天世界晴