题目描述 Description
一条街的一边有几座房子。因为环保原因居民想要在路边种些树。路边的地区被分割成块,并被编号为1…n。每个块的大小为一个单位尺寸并最多可种一裸树。每个居民想在门前种些树并指定了三个号码b,e,t。这三个数表示该居民想在b和e之间最少种t棵树。当然,b≤e,居民必须保证在指定地区不能种多于地区被分割成块数的树,即要求T≤ e-b+1。允许居民想种树的各自区域可以交叉。出于资金短缺的原因,环保部门请你求出能够满足所有居民的要求,需要种树的最少数量。
输入描述 Input Description
第一行为n,表示区域的个数;
第二行为h,表示房子的数目;
下面h行描述居民的需要:bet(0<b≤30000,r ≤e-b+ 1)分别用一个空格分开。
输出描述 Output Description
输出为满足所有要求的最少树的数量。
样例输入 Sample Input
9
4
1 4 2
4 6 2
8 9 2
3 5 2
样例输出 Sample Output
5
数据范围及提示 Data Size & Hint
【数据规模】
30%的数据满足0<n ≤1000,0<h ≤ 500; 100%的数据满足n ≤30000,h ≤5000。