Games

Time limit2sMemory limit1024 MB

Summary

Each game's rules must be learned once before unlimited replays, and the task asks for the maximum total rating reachable within d minutes.

Level: Medium6 of 10
Topics: Dynamic programming, Greedy
Solved: No attempts yet

Problem

Kile has returned from a board game fair with $n$ games. Before playing a game, he must learn its rules. Learning the rules of the $i$ -th game takes $p_i$ minutes. Once the rules are learned, the game can be played. Playing the $i$ -th game takes $t_i$ minutes. Each game also has its own rating $o_i$ .

In the coming days, Kile plans to spend at most $d$ minutes on board games. He wants the maximum sum of ratings of the games he can play. Each game can be played an arbitrary number of times.

Input

The first line contains integers $n$ and $d$ ( $1 \le n, d \le 5000$ ), the number of games and the time planned for playing games.

The $i$ -th of the following $n$ lines contains integers $p_i$ , $t_i$ and $o_i$ ( $0 \le p_i \le 5000$ , $1 \le t_i \le 5000$ , $1 \le o_i \le 10^9$ ), the time required to learn the rules, the time required to play, and the rating of the $i$ -th game.

Output

Print the maximum sum of the ratings of the games played on a single line.

Examples3

Example 1
Input
```
3 10
2 3 5
5 1 5
3 2 5
```
Expected output
```
25
```
Example 2
Input
```
4 13
0 6 5
0 3 4
0 2 3
0 4 4
```
Expected output
```
19
```
Example 3
Input
```
3 10
1 1 1
3 2 3
2 3 5
```
Expected output
```
11
```