| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 19 | 16 | 15 | 83.333% |
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ドル ≤ n, d ≤ 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ドル ≤ p_i ≤ 5000,ドル 1ドル ≤ t_i ≤ 5000,ドル 1ドル ≤ o_i ≤ 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 ≤ 10$ |
| 3 | 23 | $p_i = 0$ for all $i = 1, \dots , n$ |
| 4 | 28 | No additional constraints. |
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
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$.