题目描述

SYF 同学是我等 OI 后生的偶像，因为他是 CZYZ 第一位清华领军人物。

由于不爱运动、更不爱吃，长的像竹竿，身高 $180+$，体重 $100-$。

不过，现在的他意思到这个问题的严重性了，因为据说北京的风很大，$\dots$ 你懂得！

现在他想充分利用上大学前的暑假增肥！

这个好办，因为，CZYZ 有的是胖子，而且还是搞 OI 的，比如 WZK、ZC 等。

他们给他制定了增肥计划，提供了学校超市里的 $n$ 种卡路里很高的食物清单，让他多吃。但是，SYF 是个好小孩，他从不浪费钱，现在他的暑假零花钱只有 $m$ 分钱。

现在，就请你帮他计算一下，如何花费在m分钱内获得最多的卡路里。

输入格式

第一行两个整数 $n$ 和 $m$，表示大家提供了 $n$ 种备选食物，SYF 一共有 $m$ 分钱。

接下来 $n$ 行，每行三个整数 $w_i,s_i,t_i$，表示学校超市里这些食物的卡路里、个数和价格。

输出格式

$m$ 分钱内获得最多的卡路里

5 10
10 2 6
5 1 9
6 1 6
9 1 6
5 1 9

10

数据范围

$n \le 100$

$m \le 100000$

$1 \le w_i,t_i \le 1000000$

$1 \le s_i \le 500$