paint-the-house-5

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 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 i^th of the next N lines denotes the i^th 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 ≤ 10^5
1 ≤ D ≤ 10^11

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.

Source: hackerearth | Difficulty: MEDIUM
Tags: Fundamentals

Sorting

Ad-hoc

Greedy algorithms


Solutions:
'''
Created on 07-Jan-2016

@author: jana
'''

import sys

class Worker:
	def __init__(self,T,X,Y):
		self.T = T
		self.X = X
		self.Y = Y
		
def sort_key(a,b):
	if a.T == b.T:
		if a.Y == b.Y:
			return a.X < b.X
		return a.Y > b.Y
	return a.T < b.T

Worker.__lt__ = lambda self,other :sort_key(self, other)

no_of_workers,area_to_paint = [int(element) for element in sys.stdin.readline().split()]
list_l = []
for i in range(no_of_workers):
	element = sys.stdin.readline().split()
	list_l.append(Worker(int(element[0]),int(element[1]),int(element[2])))

list_l.sort()
area_painted = 0
best_speed= 0
cost = 0
last_time = list_l[0].T

for work in list_l:
	area_painted += best_speed*(work.T-last_time)
	if area_painted >= area_to_paint:
		break
	if best_speed < work.Y:
		best_speed = work.Y
		cost += work.X
	last_time = work.T

print(cost)