1855: 包包
文件提交：无需freopen
内存限制：512 MB
时间限制：1.000 S
评测方式：普通裁判
命题人：
提交：0
解决：0
题目描述
baobao有很多的包！但由于他过多得使用，这些包的使用期会不断地缩短。
对baobao而言，每个包都有它各自的价值ai。但每过一天，每个包都会不可避免地丢失bi的价值。
为此，baobao必须做一些防护措施，使得包的价值停止下降。对于第i个包，他需要花ci天时间来修复包，在此之后，包的价值就不会下降。
baobao每次只能修一个包，并且每天只能修一个。同时，他只能在tot天内进行维修。若有一些包坏的太快了，他可以考虑丢掉。
现在baobao向pcf询问他包的价值和最大为多少，但pcf不会做，只好把这个问题交给你了。
对baobao而言，每个包都有它各自的价值ai。但每过一天，每个包都会不可避免地丢失bi的价值。
为此，baobao必须做一些防护措施，使得包的价值停止下降。对于第i个包，他需要花ci天时间来修复包，在此之后，包的价值就不会下降。
baobao每次只能修一个包，并且每天只能修一个。同时，他只能在tot天内进行维修。若有一些包坏的太快了，他可以考虑丢掉。
现在baobao向pcf询问他包的价值和最大为多少，但pcf不会做，只好把这个问题交给你了。
输入
第一行一个整数tot和n，表示总共的天数。(n≤100,tot≤100,000)
接下来三行分别有n个整数，分别表示ai,bi,ci。
接下来三行分别有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的最优子结构性，若前一次并不是最优值，你的答案便会出错。因此尝试最优化物品加入的顺序。
包包在第2到3天修复第二个包，花费了二天。在第三天结束后，第二个包的价值固定为8-2*2=4，因此总价值为3+4=7。
注意dp的最优子结构性，若前一次并不是最优值，你的答案便会出错。因此尝试最优化物品加入的顺序。