Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
ZOJ Problem Set - 1567
Restaurant

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.

Input

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).

Output

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

55

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