题目描述

$Bob$ 在玩游戏，总共有 $n$ 款小游戏，游戏 $i$ 需要 $p_i$ 单位时间学习。学习结束后，玩一局需要 $t_i$ 单位时间，可以获得 $s_i$ 分，一款游戏学会后可以玩多次，当然也可以不玩某款游戏。

$Bob$ 想知道在 $m$ 的时间内最多可以得到多少分？

输入格式

第一行，两个正整数 $n,m$

接下来 $n$ 行，每行三个整数 $p_i,t_i,s_i$

输出格式

输出一行一个整数表示答案。

注意数据溢出。

3 10
2 3 5
5 1 5
3 2 5

25

4 13
0 6 5
0 3 4
0 2 3
0 4 4

19

3 10
1 1 1
3 2 3
2 3 5

11

样例 $3$ 解释

学第 $1,3$ 款游戏，耗时 $1+2=3$ 单位时间。

游玩游戏 $1,3,3$，获得 $1+5+5=11$ 分，耗时 $1+3+3=7$ 单位时间。

数据规模与约定

对于 $100\%$ 的数据，保证：

• $1\le n,m,t_i\le 5000$；
• $0\le p_i\le 5000$；
• $1\le s_i\le 10^9$。

• 特殊性质 A：$\forall 1\le i\le n$，$p_i=0$。