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

Submit

Source: ZOJ Monthly, March 2003