You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

背景

小明到了一个水果店里，里面有n种苹果，小明是个挑剔的人，想吃新鲜度高的苹果。现在小明有m元，想充分利用这m元，使他买到的苹果的总新鲜度最高，你能帮帮他吗？

输入

第一行输入n和m，分别表示有多少种苹果和拥有的总金额。

第二行到第n+1行，每行依次输入第i类苹果的单价a_i，单个苹果的新鲜度b_i，以及该类苹果的总数量s_i。

输出

能获得的苹果的最大新鲜度总和

样例

3 10
3 2 5
1 1 4
5 3 6

8

数据范围

0<n<=1000,0<a_i<=100,0<b_i<=100,0<s_i<=100.