Maximizing Game Score

You are given n games. For each game \(i\), you must first invest \(p_i\) minutes to learn how to play the game before you are able to play it. Once learned, you can play the game multiple times. Each time you play game \(i\), it takes \(t_i\) minutes and you earn \(o_i\) points.

You have a total of \(m\) minutes (including both learning and playing). Determine the maximum number of points you can earn by deciding which games to learn and how many times to play each game.

Example: Suppose you have 2 games and 10 minutes. For game 1, \(p_1=2\), \(t_1=3\), \(o_1=4\); for game 2, \(p_2=3\), \(t_2=2\), \(o_2=3\). One optimal strategy is to learn game 2 and then play it three times, earning a total of 9 points.

inputFormat

The first line contains two integers \(n\) and \(m\) representing the number of games and the total available minutes.

Each of the following \(n\) lines contains three integers \(p_i\), \(t_i\), and \(o_i\) representing the minutes needed to learn game \(i\), the minutes required for one round of play, and the points earned per round, respectively.

outputFormat

Output a single integer: the maximum points that can be obtained within \(m\) minutes.

sample

2 10
2 3 4
3 2 3

9