鬼吹灯之湘西疑陵

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

现有n种商品,每种商品有Si件,每种商品的价格和质量分别为Pi和Mi。你现在有钱V,问能购买的商品的总质量最大为多少。

Input

 多组输入。 对于每组输入:

第一行两个整数n,V(1 <= n <= 3,1 <= V <= 1,000,000,000)。

接下来的n行,每行三个整数Si,Pi,Mi,分别代表第i种物品的数量,价格与质量(1 <= Si <= 100,1 <= Pi <= 1,000,000,000 , 1 <= Mi <= 1,000,000,000)。

Output

 对于每组数据,输出一个整数代表答案。

Sample Input

1 10
10 1 10

Sample Output

100

Hint

Source