Kile 从桌游展会回来了。他带回了 $n$ 款游戏。在玩一款游戏之前，必须先学习它的规则。学习第 $i$ 款游戏的规则需要 $p_i$ 分钟。一旦学会了规则，就可以玩这款游戏。玩第 $i$ 款游戏需要 $t_i$ 分钟。每款游戏还有一个评分 $o_i$。
在接下来的日子里，Kile 计划花费最多 $d$ 分钟在桌游上。他想知道他能玩的游戏的评分总和最大是多少。每款游戏都可以玩任意多次。
输入格式
第一行包含整数 $n$ 和 $d$ ($1 \le n, d \le 5000$)，分别表示游戏的数量和计划花费的时间。
接下来的 $n$ 行，第 $i$ 行包含整数 $p_i, t_i$ 和 $o_i$ ($0 \le p_i \le 5000, 1 \le t_i \le 5000, 1 \le o_i \le 10^9$)，分别表示学习第 $i$ 款游戏规则所需的时间、玩该游戏所需的时间以及该游戏的评分。
输出格式
在第一行且仅一行中，输出所玩游戏评分的最大总和。
子任务
| 子任务 | 分值 | 约束条件 |
|---|---|---|
| 1 | 6 | $n = 1$ |
| 2 | 13 | $n \le 10$ |
| 3 | 23 | 对于所有 $i = 1, \dots, n$，有 $p_i = 0$ |
| 4 | 28 | 无附加约束 |
样例
输入格式 1
3 10 2 3 5 5 1 5 3 2 5
输出格式 1
25
输入格式 2
4 13 0 6 5 0 3 4 0 2 3 0 4 4
输出格式 2
19
输入格式 3
3 10 1 1 1 3 2 3 2 3 5
输出格式 3
11
说明
第三个样例的解释： 获得总分 11 的一种方式如下：在第一分钟，Kile 学习了第一款游戏，然后玩了一次。之后，他花费两分钟学习第三款游戏，并在最后 6 分钟内玩了两次。这样，所玩游戏的总分为：$1 + 5 + 5 = 11$。