Problem1001--「一本通 1.1 例 2」种树

1001: 「一本通 1.1 例 2」种树

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 16  Solved: 10
Submit Status Web Board

Creator:

Description

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

Input

第一行为 nnn,表示路段数。
第二行为 hhh,表示建议数。
下面 hhh 行描述一条建议:b,e,tb, e, tb,e,t,用一个空格分隔。

Output

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

Sample Input

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

Sample Output

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


Submit Status