아침 루틴과 아침 점호

면접 대비

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

요약

선행 단계 조건을 지키면서 총 소요 시간이 T 이하가 되도록 행동을 고르고, 만족도 합의 최댓값을 구합니다.

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

문제

오늘도 대전과학고등학교 학생들은 점호에 늦으면서 벌점을 쌓고 있다. 자신만의 체계적인 아침 루틴을 만들던 대곽이는 점호 지각으로 벌점이 $29.5$ 점이 되었다. 내일 점호에는 절대 늦으면 안 된다.

대곽이의 아침 루틴에는 $N$ 가지 행동이 있다. $i$ ( $1 \leq i \leq N$ )번째 행동은 행동의 단계를 나타내는 음이 아닌 정수 $s_i$ , 행동을 수행하는 데 걸리는 시간을 나타내는 양의 정수 $p_i$ , 행동을 수행했을 때 얻는 만족감을 나타내는 양의 정수 $h_i$ 를 가진다.

그러나 대곽이가 일어난 후 아침 점호 마감까지의 시간은 길지 않다. 따라서 대곽이는 아침 루틴을 전부 하지 못할 수도 있다. 대곽이는 행동 중 0개 이상을 골라 적절한 순서로 수행한다. 이때 수행할 행동과 순서는 다음 조건을 만족해야 한다.

대곽이는 각각의 행동을 최대 한 번 수행할 수 있다.
$i$ 번째 행동의 단계 $s_i$ 가 양의 정수인 경우, $i$ 번째 행동을 수행하기 전에 $s_i-1$ 단계의 행동을 하나 이상 수행한 적이 있어야 한다. $s_i=0$ 인 경우에는 별도의 제약이 없다.
수행한 각 행동의 소요 시간을 모두 더한 값은 점호 마감까지 남은 시간 $T$ 보다 작거나 같아야 한다.

대곽이가 얻는 만족감은 수행한 각 행동의 만족감을 모두 더한 값이다. 대곽이는 만족감이 최대가 되도록 수행할 행동과 순서를 정하고 싶어 한다. 대곽이가 최대한의 만족감을 얻도록 도와주자.

입력

첫째 줄에 대곽이의 아침 루틴에 포함된 행동의 수 $N$ 과 점호 마감까지 남은 시간 $T$ 가 공백으로 구분되어 주어진다. $(1 \leq N \leq 1000;\ 1 \leq T \leq 10000)$

다음 $N$ 개의 줄에는 각 행동의 단계 $s_i$ , 소요 시간 $p_i$ , 만족감 $h_i$ 가 공백으로 구분되어 주어진다. 단계, 소요 시간, 만족감이 같은 행동이 2개 이상 존재할 수도 있다. $(0 \leq s_i \leq 100;\ 1 \leq p_i \leq 2000;\ 1 \leq h_i \leq 100000000)$

출력

점호 마감까지 남은 시간 안에 대곽이가 얻을 수 있는 만족감의 최댓값을 출력한다.

힌트

0개의 행동을 고른 경우, 소요 시간의 합과 만족감의 합은 모두 $0$ 이다.
C/C++, Java 등의 언어에서 일부 변수를 32비트 정수형으로 선언하면 오버플로가 발생할 수 있으니 주의하라.

예제5

예제 1
입력
```
5 5
0 1 1
0 2 1
0 1 3
1 3 4
2 1 5
```
예상 출력
```
12
```
예제 2
입력
```
5 5
0 1 6
0 2 1
0 1 3
1 3 4
2 1 5
```
예상 출력
```
15
```
예제 3
입력
```
5 1
0 2 6
0 2 1
0 2 3
1 3 4
2 2 5
```
예상 출력
```
0
```
예제 4
입력
```
1 5
0 5 5
```
예상 출력
```
5
```
예제 5
입력
```
1 5
1 5 5
```
예상 출력
```
0
```