아침 루틴과 아침 점호

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