Problem1478--种树

1478: 种树

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 512 MB

Description

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

Input

第一行为 nnn,表示路段数。
第二行为 hhh,表示建议数。
下面 hhh 行描述一条建议:b,e,tb, e, tb,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%30\%30% 的数据满足 00<n100000<h500
100%100\%100% 的数据满足 00<n3×104h≤5000h\le 5000h500000<be3×104t≤e−b+1t\le e-b+1teb+1

Source/Category