Restaurant

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.
<br>
<b>Input</b><br>
<br>
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 &lt;= 100, d &lt;= 10, s &lt;= 100).</p>
<p><b><br>
Output</b><br>
<br>
One line for each test - the maximal satisfaction.</p>
<p><br>
<b>Sample Input<br>
</b><br>
5 5<br>
11 20 20<br>
12 5 21<br>
15 15 40<br>
14 13 11<br>
10 20 13</p>
<p><br>
<b>Sample Output<br>
</b><br>
55</p>
<p>Notice you don't need to consider all the dishes since some might lessen your
satisfaction.</p>
<p>Explanation of the sample<br>
10 20 13 //wait for 10 minutes<br>
11 20 20 //no wait<br>
15 15 40 /no wait<br>
14 13 11 //no wait<br>
12 5 21 //no wait<br>
satisfaction = 13 + 20 + 40 + 11 + 21 - 5*10 = 55</p>
<p><br>
</p>

ZOJ Monthly, March 2003