Problem B: 种树

Problem B: 种树

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 74  Solved: 25
[Submit] [Status] [Web Board] [Creator:]

Description

某条街被划为 n 条路段,这 n 条路段依次编号为1...n 。每个路段最多可以种一棵树。现在居民们给出了 h 组建议,每组建议包含三个整数b,e,t ,表示居民希望在路段 b 到 e 之间至少要种 t 棵树。这些建议所给路段的区间可以交叉。请问:如果要满足所有居民的建议,至少要种多少棵树。

Input

第一行为 n,表示路段数。

第二行为 h,表示建议数。

下面 h 行描述一条建议:b,e,t,用一个空格分隔。

Output

输出只有一个数,为满足所有居民的建议,所需要种树的最少数量。

Sample Input Copy

9
4
1 4 2
4 6 2
8 9 2
3 5 2

Sample Output Copy

5

HINT

 30%的数据满足 0<n≤1000,0<h≤500

 100%的数据满足 0<n≤3×10^4,h≤5000,0<b≤e3×10^4,t≤e-b+1