32949번 - 아침 루틴과 아침 점호

문제

오늘도 대전과학고등학교 학생들은 점호에 늦으면서 벌점을 축적하고 있다. 자신만의 체계적인 아침 루틴을 개발하다가 점호 지각으로 어느새 벌점이 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ドル$비트 정수형으로 선언한 경우 오버플로우가 발생할 수 있음에 유의하라.