레이팅 미적용Kile has returned from a board game fair. He brought home \(n\) games. Before
playing a game, it is necessary to learn its rules. Learning the rules of the \(i\)-th
game takes \(p_{i}\) minutes. Once the rules are learned, it is possible to play the game.
Playing the \(i\)-th game takes \(t_{i}\) minutes. Each game also has its own rating \(o_{i}\).
In the coming days, Kile has planned to spend at most \(d\) minutes on board games.
He is interested in finding out the maximum sum of the ratings of the games he
can play. Each game can be played an arbitrary number of times.
The first line contains integers \(n\) and \(d\) (\(1 \le n\), \(d \le 5000\)), the number of games and the time planned to
spend on playing games.
The \(i\)-th of the following n lines contains integers \(p_{i}\), \(t_{i}\) and \(o_{i}\) (\(0 \le p_{i} \le 5000\), \(1 \le t_{i} \le 5000\), \(1 \le o_{i} \le 10^{9}\)),
time required to learn the rules, time required to play and the rating of \(i\)-th game.
In the first and only line, output the maximum sum of the ratings of the games played.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 6점 | \(n = 1\) |
2 | 13점 | \(n \le 10\) |
3 | 23점 | \(p_{i} = 0\) for all \(i = 1\), ..., n |
4 | 28점 | No additional constraints. |
3 10
2 3 5
5 1 5
3 2 5254 13
0 6 5
0 3 4
0 2 3
0 4 4193 10
1 1 1
3 2 3
2 3 511Clarification of the third example:
One way to achieve a total score of 11 is as follows: in the first minute, Kile learns to play the first game,
then plays it once. After that, he spends two minutes learning to play the third game, and in the last 6
minutes, he plays it twice. This way, the total score of the games played is: 1 + 5 + 5 = 11.