Welcome to ZOJ
Select Problem
ZOJ Problem Set - 1567

Time Limit: 5 Seconds      Memory Limit: 32768 KB

The other day all the team members are having dinner together at a restaurant. As the restaurant is quite small, they've got few cooks and the waiting seems a bit endless. The good point is we know exact how long each dish will cost the restaurant to prepare, and also how long each dish will be finished. :P Let's define ta the time to prepare a dish, and tb the time to eat a dish, whereas s the satisfaction you get. Of course when there is no dish on the table, we get annoyed a lot and de-satisfy at a rate of d per second. Now given all the numbers, you are to find out the maximal satisfaction we can get out of this restaurant.


There are multiple tests. Each test starts with a line of two integers, n - the number of dishes available at the restaurant, and d - the de-satisfaction per minute without dishes. The following n lines contains three integers each, ta, tb and s. ta and tb are in minutes. (n <= 100, d <= 10, s <= 100).


One line for each test - the maximal satisfaction.

Sample Input

5 5
11 20 20
12 5 21
15 15 40
14 13 11
10 20 13

Sample Output


Notice you don't need to consider all the dishes since some might lessen your satisfaction.

Explanation of the sample
10 20 13 //wait for 10 minutes
11 20 20 //no wait
15 15 40 /no wait
14 13 11 //no wait
12 5 21 //no wait
satisfaction = 13 + 20 + 40 + 11 + 21 - 5*10 = 55

Author: CHEN, Gaoli
Source: ZOJ Monthly, March 2003
Submit    Status