A回--背包--最大收益

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

新年伊始,我飞瞅准机会要大赚一笔,于是我飞换了一个体积为V的背包。

 

现在有N种商品,每种商品有Mi件,可以带来的收益为Pi,体积为Vi

那么问题来了,在所装物品不超过V的前提下的最大收益是多少?

谁能快速的做帮我飞算出来,我飞就让谁出任UFO,迎娶高富帅,走上人生巅峰233。各位准Final巨巨加油啊。

Input

 第一行输入一个T,代表有T(1 <= T <= 15)组数据。

对于每一组数据:

第一行有两个整数N , V

接下里的N行,每行三个整数MiViPi

对于所有数据1 <= N <= 200,1 <= V <= 15000,1 <= Mi , Vi, Pi <= 100000

Output

 对于每组数据输出一个整数,代表我飞的最大收益。

Sample Input

1
2 10
1 10 10
2 6 21

Sample Output

21

Hint

 

Source

zmx