Tom has decided she would like to buy the brand new iTone Duo, but to even buy the base model it might cost an arm and a leg, maybe even a kidney or liver. Luckily, due to medical advancements, Tom is able to quickly and easily sell such body parts and have them repeatedly regenerate, each time taking the same amount of time. However, each body part may only regenerate a certain amount of times. Initially, Tom starts off with all sellable body parts.

Each of Tom's body parts has a certain monetary value, and a certain amount of time required to regenerate. Every time a body part regenerates, Tom can sell it again for its stated value. Selling a body part takes no time. How long will it take Tom to be able to afford the new iTone?

Input

The first line consists of two integers ~n~ (~1 \leq n \leq 100~), and ~m~ (~1 \leq m \leq 10^9~), the number of body parts that Tom can sell, and the cost of the iTone Duo.

The next ~n~ lines each contain three integers ~c_i~, ~x_i~, and ~r_i~. The ~i~-th body part can be sold for ~c_i~ dollars whenever it is available. It is initially available at time ~0~. After being sold, it regenerates and becomes available after ~r_i~ seconds. It can regenerate at most ~x_i~ times, so it can be sold at most ~x_i+1~ times. ~(1 \leq c_i, x_i, r_i \leq 10^5~).

Output

Output the minimum non-negative number of seconds after which Tom can afford the iTone Duo. If it is impossible for Tom to afford it no matter the amount of time, output -1.

Examples

Input 1

2 20
4 1 1
4 3 4

Output 1

8

At ~t=0~, Tom can instantly sell both intially available body parts for a total of ~8~ dollars.

At ~t=1~, the first sold body part has been regenerated, and can be sold again instantly. This brings Tom's total to ~12~ dollars. Note that this body part won't regenerate again at ~t=2~ because it has already regenerated the maximum number of times.

At ~t=4~, the second sold body part has been regenerated, and can be sold again instantly. This brings Tom's total to ~16~ dollars.

At ~t=8~, the second sold body part has been regenerated, and can be sold again instantly. This brings Tom's total to ~20~ dollars, able to afford the iTone Duo.

Input 2

2 20
1 1 1
1 1 4

Output 2

-1

Tom cannot regenerate enough body parts to make ~20~ dollars.