게임

시간 제한2초메모리 제한1024 MB

요약

각 게임은 규칙을 한 번 배운 뒤 여러 번 할 수 있으며, d분 안에서 얻을 수 있는 최대 평점의 합을 구합니다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 그리디
정답자: 아직 제출이 없습니다

문제

킬레는 보드게임 박람회에서 게임을 $n$ 개 가지고 돌아왔다. 게임을 하기 전에는 규칙을 먼저 배워야 한다. $i$ 번째 게임의 규칙을 배우는 데 $p_i$ 분이 걸린다. 규칙을 배우고 나면 그 게임을 할 수 있다. $i$ 번째 게임을 하는 데는 $t_i$ 분이 걸린다. 각 게임에는 평점 $o_i$ 가 있다.

앞으로 킬레는 보드게임에 최대 $d$ 분을 쓰려고 한다. 킬레가 할 수 있는 게임들의 평점 합의 최댓값을 구하는 문제다. 각 게임은 원하는 만큼 몇 번이든 할 수 있다.

입력

첫째 줄에 정수 $n$ 과 $d$ 가 주어진다 ( $1 \le n, d \le 5000$ ). $n$ 은 게임의 수이고, $d$ 는 게임에 쓸 수 있는 시간(분)이다.

이어지는 $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$ ). 각각 규칙을 배우는 데 걸리는 시간, 게임을 하는 데 걸리는 시간, 평점이다.

출력

할 수 있는 게임들의 평점 합의 최댓값을 첫째 줄에 출력한다.

예제3

예제 1
입력
```
3 10
2 3 5
5 1 5
3 2 5
```
예상 출력
```
25
```
예제 2
입력
```
4 13
0 6 5
0 3 4
0 2 3
0 4 4
```
예상 출력
```
19
```
예제 3
입력
```
3 10
1 1 1
3 2 3
2 3 5
```
예상 출력
```
11
```