飞花巨巨馋了

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

 我啸51期间去杭州游玩,顺便比赛。

经过查询,去杭州要坐十几个小时的火车啊,身为巨巨的我啸肯定不能亏待了自己,所以在去杭州之前准备采购一番,让自己能舒舒服服的度过这十几个小时,所以,我啸来到了干果店,准备买一些干果到路上吃,干果店的标价有点特殊,xxx p q:代表xxx这种干果1块钱可以买p (kg),当前库存共有q (kg),我啸因为经费不够,不能任性,所以只能尽量买多一点干果。

Input

        多组输入,第1行为两个整数n c(0 <= n <= 100 , 0 <= c <= 10000 ),代表干果店中有n种干果,和我啸一共带了c元钱。

之后第2到第n+1行,每行为:

xxx p q(xxx为字符串,长度<=100,p,q为整数,q是p的整数倍,1 <= p <= 10 , 0 <= q <= 100 )

代表xxx这种干果1块钱可以买p (kg),当前库存共有q (kg)

Output

 每组数据输出一行,能买到的最多的干果重量

Sample Input

2 10
aaa 1 5
bbb 2 2
3 10
aaa 1 5
bbb 2 10
ccc 3 9

Sample Output

7
21

Hint

Source

winddream