Morning Routine and Roll Call

Interview

Time limit1.5sMemory limit1024 MB

Summary

Choose actions whose stage prerequisites are met and whose total time is at most T, then output the maximum total satisfaction.

Level: Medium5 of 10
Topics: Dynamic programming, Array
Solved: No attempts yet

Problem

Even today, students at Daejeon Science High School keep piling up demerit points for arriving late to roll call. Daegwak has been developing his own systematic morning routine, but a late arrival at roll call has already brought his demerit points to $29.5$ . He must never be late for tomorrow's roll call.

Daegwak's morning routine has $N$ actions. The $i$ -th action ( $1 \leq i \leq N$ ) has a stage $s_i$ , a non-negative integer; a time $p_i$ , a positive integer for how long the action takes; and a satisfaction value $h_i$ , a positive integer for the satisfaction he gets from performing it.

The time from when Daegwak wakes up until the roll call deadline is not very long, so he may not be able to finish the entire routine. He chooses zero or more actions and performs them in a suitable order. The actions he performs must satisfy these conditions.

Daegwak can perform each action at most once.
If the stage $s_i$ of the $i$ -th action is a positive integer, Daegwak must have performed at least one action of stage $s_i-1$ before performing the $i$ -th action. If $s_i=0$ , there is no additional constraint.
The sum of the times needed for the actions he performs must be less than or equal to the remaining time $T$ before the roll call deadline.

The satisfaction Daegwak gets is the sum of the satisfaction values of the actions he performs. He wants to choose the actions and their order to maximize this sum. Help him reach the maximum satisfaction.

Input

The first line contains $N$ and $T$ , separated by a space. $(1 \leq N \leq 1000;\ 1 \leq T \leq 10000)$

Each of the next $N$ lines contains $s_i$ , $p_i$ , and $h_i$ , separated by spaces. Two or more actions may have the same stage, time, and satisfaction value. $(0 \leq s_i \leq 100;\ 1 \leq p_i \leq 2000;\ 1 \leq h_i \leq 100000000)$

Output

Print the maximum satisfaction Daegwak can get within the remaining time before the roll call deadline.

Hint

If Daegwak chooses zero actions, the sum of the times and the sum of the satisfaction values are both $0$ .
In languages such as C, C++, and Java, declaring some variables as 32-bit integers can cause overflow. Be careful.

Examples5

Example 1
Input
```
5 5
0 1 1
0 2 1
0 1 3
1 3 4
2 1 5
```
Expected output
```
12
```
Example 2
Input
```
5 5
0 1 6
0 2 1
0 1 3
1 3 4
2 1 5
```
Expected output
```
15
```
Example 3
Input
```
5 1
0 2 6
0 2 1
0 2 3
1 3 4
2 2 5
```
Expected output
```
0
```
Example 4
Input
```
1 5
0 5 5
```
Expected output
```
5
```
Example 5
Input
```
1 5
1 5 5
```
Expected output
```
0
```