时间限制：1秒　　内存限制：256M

---

【题目描述】

　　小沐的油漆队有 \(K\) 个漆匠，由于年龄、技术的差别，所以不同的人粉刷一块单位长的木板收费可能不同，漆匠 \(i\) 粉刷一块单位长的木板收费为 \(P_i\) 元。

　　客户小原有 \(N\) 块单位长的木板需要粉刷，这些木板排成一排，并从左到右编号为 \(1..N\)。小沐接到这个业务之后，安排 \(K\) 个漆匠站在木板的不同位置，漆匠 \(i\) 站在第 \(S_i\) 块木板处，且他能粉刷的木板数量不超过 \(L_i\) 块，当然他只能粉刷他面前的连续的若干块木板，且必须包含第 \(S_i\) 块木板。

　　作为团队领导，漆匠们的收入都应上缴到小沐这里，提成后，再以工资的发放给漆匠们。所以请你帮他计算，应怎样安排这些工人粉刷木板，才能获得最大收益。要求不能有木板被多人粉刷的情况，但允许有些木板不被粉刷和漆工不粉刷任何木版的情况。

【输入格式】

　　第一行包含连个整数 \(N,K\)，其意义如题目描述。接下来的 \(K\) 行，每行包含 3 个整数 \(L_i,P_i,S_i\)，分别表示漆匠 \(i\) 能粉刷的木板的数量、粉刷一块木板的收费和他所在的位置。

【输出格式】

　　一个整数，表示最大收益。

【输入输出样例】

　Input

8 4
3 2 2
3 2 3
3 3 5
1 1 7 

　Output

17

【数据限制】

　　\(100\%\) 的数据满足：\(1 ≤ N ≤ 1000000\)，\(1≤K≤100\)，\(1≤P_i≤10000\)。

【来源】

　　Mr.he