P2021 [第一章例题1.2]种树
描述
一条街道的一边有几座房子。因为环境原因居民想要在路边种些树,路边的地区被分割成 块,并被编号为 ,每块大小为一个单位尺寸并最多可种一棵树。每个居民想在门前种些树并指定了三个数 ,这三个数分别表示该居民想在 到 之间最少要种 棵树。当然,,允许居民想种树的子区域可以交叉。处于资金紧缺的原因,环保部门请你求出能够满足所有居民的种树要求时所需要种的树的最少数量。
输入
第一行为 ,表示区域的个数。
第二行为 ,表示房子的数目。
下面 行描述居民的需要:、、分别用一个空格分开。
输出
输出一个数,为满足所有居民的要求,所需要种树的最少数量。
样例输入
9
4
1 4 2
4 6 2
8 9 2
3 5 2
样例输出
5
提示
数据范围
的数据满足 。
的数据满足 。