问题 26003 --种树

26003: 种树

时间限制: 1 Sec  内存限制: 128 MB
提交: 74  解决: 24
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][71760kb]

题目描述

为了绿化乡村,H村积极响应号召,开始种树了。
H村里有n幢房屋,这些屋子的排列顺序很有特点,在一条直线上。于是方便起见,我们给它们标上1~n。树就种在房子前面的空地上。
同时,村民们向村长提出了m个意见,每个意见都是按如下格式:希望第li个房子到第ri个房子的房前至少有ci棵树。
因为每个房屋前的空地面积有限,所以每个房屋前最多只能种ki棵树。
村长希望在满足村民全部要求的同时,种最少的树以节约资金。请你帮助村长。

输入

输入文件名为tree.in 
输入第1行,包含两个整数n,m。
第2行,有n个整数ki。
第2~m+1行,每行三个整数li,ri,ci。

输出

输出文件名为tree.out 
输出1个整数表示在满足村民全部要求的情况下最少要种的树。村民提的要求是可以全部满足的。

样例输入

5 3 
1 1 1 1 1 
1 3 2 
2 4 2 
4 5 1

样例输出

3

提示

【输入输出样例解释1】 

如图是满足样例的其中一种方案,最少要种3棵树。







【输入输出样例2】






【输入输出样例2】tree.in                               



4 3



3 2 4 1



1 2 4



2 3 5



2 4 6                               



tree.out



8



【输入输出样例解释2】









如图是满足样例的其中两种方案,左图的方案需要种9棵树,右图的方案需要种8棵树。可以验证,最少需要种8棵树。



【数据范围】



对于30%的数据,0<n≤100,0<m≤100,ki=1;



对于50%的数据,0<n≤2,000,0<m≤5,000,0<ki≤100;



对于70%的数据,0<n≤50,000,0<m≤100,000,0<ki≤1,000;



对于100%的数据,0<n≤500,000,0<m≤500,000,0<ki≤5,000


来源

[提交][状态]