2421: 包包

baobao有很多的包！但由于他过多得使用，这些包的使用期会不断地缩短。 
对baobao而言，每个包都有它各自的价值ai。但每过一天，每个包都会不可避免地丢失bi的价值。 
为此，baobao必须做一些防护措施，使得包的价值停止下降。对于第i个包，他需要花ci天时间来修复包，在此之后，包的价值就不会下降。 
baobao每次只能修一个包，并且每天只能修一个。同时，他只能在tot天内进行维修。若有一些包坏的太快了，他可以考虑丢掉。 
现在baobao向pcf询问他包的价值和最大为多少，但pcf不会做，只好把这个问题交给你了。 

第一行一个整数tot和n，表示总共的天数。(n≤100,tot≤100,000) 
接下来三行分别有n个整数，分别表示ai,bi,ci。

5 2
5 10
2 2
1 2

7

包包在第1天修复第一个包，花费了一天。在第一天结束后，第一个包的价值固定为5-2=3，第二个包的价值变为10-2=8。
包包在第2到3天修复第二个包，花费了二天。在第三天结束后，第二个包的价值固定为8-2*2=4，因此总价值为3+4=7。
注意dp的最优子结构性，若前一次并不是最优值，你的答案便会出错。因此尝试最优化物品加入的顺序。