You want to repaint your house entirely for an upcoming occasion. The total area of your house is D units. There are a total of N workers. The i^th worker has his available time T_i, hiring cost X_i and speed Y_i. This means that he is available for hiring from time T_i and remains available ever since. Once available, you can hire him with cost X_i, after which he will start painting the house immediately, covering exactly Y_i units of house with paint per time unit. You may or may not hire a worker and can also hire or fire him at any later point of time. However, no more than 1 worker can be painting the house at a given time.

Since you want the work to be done as fast as possible, figure out a way to hire the workers, such that your house gets painted at the earliest possible time, with minimum cost to spend for hiring workers.

Note: You can hire a previously hired worker without paying him again.

INPUT

The first line of input contains two integers "N D", the number of workers and the area of your house respectively. The i^th of the next N lines denotes the i^th worker, and contains three integers "T_i X_i Y_i", described in the statement.

OUTPUT

Output one integer, the minimum cost that you can spend in order to get your house painted at the earliest.

CONSTRAINTS

1 ≤ N, T, X, Y ≤ 10⁵
1 ≤ D ≤ 10¹¹