아침 루틴과 아침 점호

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

요약

총 소요 시간이 T 이하가 되도록 행동을 골라 수행하되, 단계 s인 행동은 단계 s-1 행동을 하나 이상 이미 수행한 뒤에만 할 수 있을 때 만족감 합의 최댓값을 구한다.

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

문제

오늘도 대전과학고등학교 학생들은 점호에 늦으면서 벌점을 축적하고 있다. 자신만의 체계적인 아침 루틴을 개발하다가 점호 지각으로 어느새 벌점이 $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 1 \\, 000;$ $1 \leq T \leq 10 \\, 000)$

다음 $N$ 개의 줄에는 각 행동의 단계 $s\_i$ , 행동을 수행하는 데에 걸리는 시간 $p\_i$ , 행동을 수행했을 때 얻는 만족감 $h\_i$ 가 공백으로 구분되어 주어진다. 단계, 소요 시간, 만족감이 같은 행동이 $2$ 개 이상 존재할 수도 있다. $(0 \leq s\_i \leq 100;$ $1 \leq p\_i \leq 2 \\, 000;$ $1 \leq h\_i \leq 100 \\, 000 \\, 000)$

출력

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

힌트

$0$ 개의 행동을 고른 경우 각각의 행동을 수행하는 데에 걸리는 시간의 합과, 수행한 각각의 행동을 수행했을 때 얻는 만족감의 합은 모두 $0$ 이다.
C/C++, Java 등의 언어에서 일부 변수를 $32$ 비트 정수형으로 선언한 경우 오버플로우가 발생할 수 있음에 유의하라.

예제7

예제 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
```
예제 6
입력
```
2 5
0 5 5
1 6 5
```
예상 출력
```
5
```
예제 7
입력
```
2 10
0 1 2
0 1 2
```
예상 출력
```
4
```