A22731.种树
普及-
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
一条街的一边有几座房子,因为环保原因居民想要在路边种些树。路边的地区被分割成块,并被编号成 1,2,…,n。每个部分为一个单位尺寸大小并最多可种一棵树。
每个居民都想在门前种些树,并指定了三个号码 b,e,t。这三个数表示该居民想在地区 b 和 e 之间(包括 b 和 e)种至少 t 棵树。
居民们想种树的各自区域可以交叉。你的任务是求出能满足所有要求的最少的树的数量。
输入格式
输入的第一行是一个整数,代表区域的个数 n。
输入的第二行是一个整数,代表房子个数 h。
第 3 到第 (h+2) 行,每行三个整数,第 (i+2) 行的整数依次为 bi,ei,ti,代表第 i 个居民想在 bi 和 ei 之间种至少 ti 棵树。
输出格式
输出一行一个整数,代表最少的树木个数。
输入输出样例
输入#1
9 4 1 4 2 4 6 2 8 9 2 3 5 2
输出#1
5
说明/提示
数据规模与约定
对于 100% 的数据,保证:
- 1≤n≤3×104,1≤h≤5×103。
- 1≤bi≤ei≤n,1≤ti≤ei−bi+1。