igre (COCI CONTEST_#2)
Time limit: 2 seconds | Memory limit: 512 MB | Task type: batch
Algorithms: knapsack dp

# Task Igre

Kile has returned from a board game fair. He brought home $n$ games. Before playing a game, it is necessary to learn its rules. Learning the rules of the $i$-th game takes $p_i$ minutes. Once the rules are learned, it is possible to play the game. Playing the $i$-th game takes $t_i$ minutes. Each game also has its own rating $o_i$.

In the coming days, Kile has planned to spend at most $d$ minutes on board games. He is interested in finding out the maximum sum of the ratings of the games he can play. Each game can be played an arbitrary number of times.

![](_page_0_Picture_6.jpeg)

# Input

The first line contains integers $n$ and $d$ ($1 \le n, d \le 5000$), the number of games and the time planned to spend on 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$), time required to learn the rules, time required to play and the rating of $i$-th game.

# Output

In the first and only line, output the maximum sum of the ratings of the games played.

## Scoring

| Subtask | Points | Constraints             |
| :------ | :----- | :---------------------- |
| 1       | 6      | $n = 1$                 |
| 2       | 13     | $n \le 10$              |
| 3       | 23     | $p_i = 0$ for all $i$   |
| 4       | 28     | No additional constraints |

## Examples

| Input | Input | Input |
| :---- | :---- | :---- |
| 3 10  | 4 13  | 3 10  |
| 2 3 5 | 0 6 5 | 1 1 1 |
| 5 1 5 | 0 3 4 | 3 2 3 |
| 3 2 5 | 0 2 3 | 2 3 5 |
|       | 0 4 4 |       |
| Output| Output| Output|
| 25    | 19    | 11    |

## Clarification

One way to achieve a total score of 11 is as follows: in the first minute, Kile learns to play the first game, then plays it once. After that, he spends two minutes learning to play the third game, and in the last 6 minutes, he plays it twice. This way, the total score of the games played is: 1 + 5 + 5 = 11.

Starter code:

Grader code:

Setup script:

Evaluation script: