U509909 [COCI2024/2025 #2] Igre

Kile 从一个棋盘游戏博览会上回来了。他带回了 n 场比赛。在玩一场比赛之前，需要学习它的规则。学习第 $i$ 场比赛的规则需要 $p_i$ 分钟。一旦学习了规则，就可以玩这个游戏。玩第 $i$ 场比赛需要 $t_i$ 分钟。每个游戏也有自己的评分 $o_i$。 在接下来的几天里，Kile 计划最多花 $d$ 分钟玩棋盘游戏。他感兴趣的是找出他能玩的游戏评级的最大和。每个游戏可以玩任意次数。

第一行输入两个正整数 $n$ 和 $k$，表示有几款游戏、在这个游戏上愿意花多长时间。 之后的 $n$ 行，每行三个正整数 $p_i$、$t_i$ 和 $o_i$，分别表示学习规则的时间、需要玩多长时间和第 $i$ 款游戏的评分。

仅一行，输出游戏评级的最大和。

【样例解释 #1】 实现总分 $11$ 的一种方法是：在第 $1$ 分钟，Kile 学会玩第一局游戏，然后玩一次。之后，他花 $2$ 分钟学习玩第三局游戏，在最后的 $6$ 分钟里，他玩两次。这样，所玩游戏的总分是：$1+5+5=11$。 【数据范围】 对于 $100\%$ 的数据，$1\le n,d,p_i,t_i\le 5000,1\le o_i\le 10^9$。 | Substask | 分数 | 约束条件 | | :----------: | :----------: | :----------: | | $0$ | $0$ | 样例 | | $1$ | $6$ | $n=1$ | | $2$ | $13$ | $n\le10$ | | $3$ | $23$ | $p_i=0$ | | $4$ | $28$ | 无 |