Description

Altynai是一个纯正的DOTA菜鸟..而且他玩DOTA有一个特点,就是特别喜欢那些DPS(每秒输出的伤害)高的英雄..

而且买的装备也是专门买那种加攻击力加的很多的装备.. = =

现在他又在玩DOTA了..由于一开始杀了很多次敌方的英雄和小兵,Altynai现在身上有一些小钱了..

现在他开心的回自己的基地准备买装备了..由于有限制,他身上最多能带6个装备,而且每种装备他最多买一件..

由于时间紧迫,他必须抓紧时间来买装备,从而能使自己的攻击力增加的最多..当然了,Altynai不在意花了多少钱..

毕竟他最在意的是能增加的攻击力!

请你帮帮Altynai,算一下他能增加的最大的攻击力.

Input

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

Output

算一下他能增加的最大的攻击力.

Sample

Input

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

Output

1080

Source: 1.天世界晴