题目描述

baobao 有很多的包！但由于他过多得使用，这些包的使用期会不断地缩短。

对baobao而言，每个包都有它各自的价值 $a_i$。但每过一天，每个包都会不可避免地丢失 $b_i$ 的价值。

为此，baobao 必须做一些防护措施，使得包的价值停止下降。对于第 $i$ 个包，他需要花 $c_i$ 天时间来修复包，在此之后，包的价值就不会下降。

baobao 每次只能修一个包，并且每天只能修一个。同时，他只能在 $tot$ 天内进行维修。若有一些包坏的太快了，他可以考虑丢掉。

现在 baobao 向 pcf 询问他包的价值和最大为多少，但 pcf 不会做，只好把这个问题交给你了。

输入格式

第一行一个整数 $tot$ 和 $n$，表示总共的天数。(n≤100,tot≤100,000)

接下来三行分别有 $n$ 个整数，分别表示 $ai$,$b_i$,$c_i$。

输出格式

一个整数，表示最优的答案。

5 2
5 10
2 2
1 2

7

提示

包包在第 $1$ 天修复第一个包，花费了一天。在第一天结束后，第一个包的价值固定为 $5-2=3$，第二个包的价值变为 $10-2=8$。

包包在第 $2$ 到 $3$ 天修复第二个包，花费了二天。在第三天结束后，第二个包的价值固定为 $8-2 \times 2=4$，因此总价值为 $3+4=7$。

注意 $dp$ 的最优子结构性，若前一次并不是最优值，你的答案便会出错。因此尝试最优化物品加入的顺序。