P96523

种树

难度 未定
讨论 统计 9通过 27提交 33.3%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

一条街道的一边有几座房子。因为环保原因居民想要在路边种些树,路边的地区被分割成n块,并被编号为1…n,每块大小为一个单位尺寸并最多可种一棵树。每个居民想在门前种些树并制定了三个数b,e,t这三个数分别表示该居民想在b和e之间最少种t棵树,当然,b≤e,t≤e-b+1,允许居民想种树的子区域可以交叉。出于资金紧缺的原因,环保部门请你求出能够满足所有居民的种树要求时所需要种的树的最少数量。

输入

第一行为n,表示区域的个数。

第二行为h,表示房子的数目。

下面h行描述居民的需要:b、e、t(0<b≤e30000,t≤e-b+1)分别用一个空格分开。

输出

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

样例

样例 1
输入
9
4
1 4 2
4 6 2
8 9 2
3 5 2
输出
5

来源

一本通

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交