Paint the house
Tag(s):

Ad-Hoc, Basic Programming, Greedy algorithm, Medium, Sorting

Problem
Editorial
Analytics

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 ith worker has his available time Ti, hiring cost Xi and speed Yi. This means that he is available for hiring from time Ti and remains available ever since. Once available, you can hire him with cost Xi, after which he will start painting the house immediately, covering exactly Yi 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 ith of the next N lines denotes the ith worker, and contains three integers "Ti Xi Yi", 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 ≤ 105
1 ≤ D ≤ 1011

SAMPLE INPUT
3 3
1 1 1
2 2 2
3 1 5
SAMPLE OUTPUT
3
Explanation

We can hire the first worker at cost of 1 and second at cost of 2, to finish painting at the minimum time of exactly 2 time units.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...