2503: 种树
内存限制：256 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：11
解决：5
题目描述
为了绿化乡村,H村积极响应号召,开始种树了。
H村里有n幢房屋,这些屋子的排列顺序很有特点,在一条直线上。于是方便起见,我们给它
们标上1~n。树就种在房子前面的空地上。
同时,村民们向村长提出了m个意见,每个意见都是按如下格式:希望第L i 个房子到第R i 个房
子的房前至少有C i 棵树。
因为每个房屋前的空地面积有限,所以每个房屋前最多只能种K i 棵树。
村长希望在满足村民全部要求的同时,种最少的树以节约资金。现在请你编程帮助村长解决
这个问题。
输入
第1行,包含两个整数n,m。
第2行,有n个整数K i 。
第2~m+1行,每行三个整数L i ,R i ,C i 。
输出
输出一行一个整数,表示在满足村民全部要求的情况下最少要种的树。
样例输入 复制
5 3
1 1 1 1 1
1 3 2
2 4 2
4 5 1样例输出 复制
3提示
如图是满足样例的其中一种方案,最少要种3棵树:
【 输 入 样 例 2】
4 3
3 2 4 1
1 2 4
2 3 5
2 4 6
【 输 出 样 例 2】
8
如图是满足样例的其中两种方案,上图的方案需要种9棵树,下图的方案需要种8棵树。
可以验证,最少需要种8棵树。
对于30%的数据, 0<n≤100,0<m≤100,K i =1;
对于50%的数据, 0<n≤2000,0<m≤5000,0
对于70%的数据, 0<n≤50000,0<m≤100000,0
对于100%的数据,0<n≤500000,0<m≤500000,0