2393 - 种树

题目描述

一条街道的一边有几座房子。因为环保原因居民想要在路边种些树,路边的地区被分割成 nn 块,并被编号为 1...n1...n,每一块大小为一个单位尺寸并最多可种一棵树。每个居民想在门前种些树并指定了三个数 betb,e,t 这三个数分别表示该居民想在 bbee 之间最少种 tt 棵树,当然,beb ≤ eteb+1t ≤ e - b + 1,允许居民想种树的子区域可以交叉。

出于资金紧缺的原因,环保部门请你求出能够满足所有居民的树所需种的树的最少数量。

输入

第一行为 nn,表示区域的个数;

第二行为 hh ,表示房子的数目;

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

输出

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

样例

输入
复制

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

输出
复制

5
说明

30%30\% 的数据满足 0<n10000 < n ≤ 10000<h5000 < h ≤ 500

100%100\% 的数据满足 0<n300000 < n ≤ 300000<h50000 < h ≤ 5000

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 0
通过人数 0
金币数量 2 枚
难度 基础


上一题 下一题