시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB20171684.211%

문제

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.

서브태스크

번호배점제한
16

$n = 1$

213

$n ≤ 10$

323

$p_i = 0$ for all $i = 1, \dots , n$

428

No additional constraints.

예제 입력 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

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$.

채점 및 기타 정보

  • 예제는 채점하지 않는다.