E. Final Showdown
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Within a well-known video game, our hero faces "The Beast", the final boss of the game, and wants to know if he is capable of defeating her or not.

The hero has $$$P$$$ power points and has $$$N$$$ different weapons at his disposal. Each weapon is characterized by three integers $$$A$$$, $$$B$$$, and $$$C$$$. When attacking with a weapon, if the hero currently has $$$P$$$ power points, he will have $$$\displaystyle{\left \lfloor \frac{P-B}{A}\right \rfloor}$$$ power points after the attack, inflicting damage to The Beast such that she loses $$$C$$$ health points. After hitting The Beast, the weapons break. For this reason, each weapon can be used at most once.

The hero wins the confrontation if he manages to defeat The Beast. To achieve this, his power points must be non-negative, and The Beast's health points must be zero or negative.

What is the maximum amount of health points $$$V$$$ that The Beast can initially have for the hero to be able to defeat her?

Note: $$$\lfloor x \rfloor$$$ is the largest integer such that $$$\lfloor x \rfloor \leq x$$$. For example, $$$\lfloor 2.5 \rfloor=2, \lfloor \pi \rfloor=3, \lfloor -2.75 \rfloor=-3$$$.

Input

A line with two integers $$$N$$$ and $$$P$$$ $$$(1 \leq N \leq 200, 1 \leq P \leq 10^5)$$$, the number of weapons and the initial amount of power points of the hero.

Then $$$N$$$ lines that describe the weapons with three integers $$$A$$$, $$$B$$$, and $$$C$$$ $$$(1 \leq A, B, C \leq 10^5)$$$.

Output

A line with an integer $$$V$$$, the maximum amount of health points that The Beast can have.

Examples
Input
3 66
8 8 6
8 8 9
2 5 2
Output
11
Input
2 10
3 1 4
2 8 6
Output
10
Input
1 6
3 7 5
Output
0
Note

In the first example, if The Beast has $$$11$$$ health points, the hero can use the second weapon, reducing his power points from $$$66$$$ to $$$\lfloor \frac{66-8}{8}\rfloor=7$$$ and The Beast's health points to $$$2$$$. Then, he can use the third weapon, reducing his power points from $$$7$$$ to $$$\lfloor \frac{7-5}{2}\rfloor=1$$$ and The Beast's health points to $$$0$$$. If The Beast starts with $$$12$$$ health points or more, then it is impossible to defeat her.

In the second example, if The Beast has $$$10$$$ health points, the hero can first use the second weapon and then the first, reducing his power points to $$$0$$$ and The Beast's health points to $$$0$$$.

In the third example, the only way for the hero to win is if The Beast has $$$0$$$ health points initially.