10029: 种树（多测试点）
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：1
Solved：0
Description
为了绿化乡村，H村积极响应号召，开始种树了。
H村里有n幢房屋，这些屋子的排列顺序很有特点，在一条直线上。于是方便起见，我们给它们标上1~n。树就种在房子前面的空地上。
同时，村民们向村长提出了m个意见，每个意见都是按如下格式：希望第li个房子到第ri个房子的房前至少有ci棵树。
因为每个房屋前的空地面积有限，所以每个房屋前最多只能种ki棵树。
村长希望在满足村民全部要求的同时，种最少的树以节约资金。请你帮助村长。
H村里有n幢房屋，这些屋子的排列顺序很有特点，在一条直线上。于是方便起见，我们给它们标上1~n。树就种在房子前面的空地上。
同时，村民们向村长提出了m个意见，每个意见都是按如下格式：希望第li个房子到第ri个房子的房前至少有ci棵树。
因为每个房屋前的空地面积有限，所以每个房屋前最多只能种ki棵树。
村长希望在满足村民全部要求的同时，种最少的树以节约资金。请你帮助村长。
Input
输入文件名为tree.in
输入第1行，包含两个整数n，m。
第2行，有n个整数ki。
第2~m+1行，每行三个整数li，ri，ci。
输入第1行，包含两个整数n，m。
第2行，有n个整数ki。
第2~m+1行，每行三个整数li，ri，ci。
Output
输出文件名为tree.out
输出1个整数表示在满足村民全部要求的情况下最少要种的树。村民提的要求是可以全部满足的。
输出1个整数表示在满足村民全部要求的情况下最少要种的树。村民提的要求是可以全部满足的。
Sample Input Copy
5 3
1 1 1 1 1
1 3 2
2 4 2
4 5 1Sample Output Copy
3HINT
【输入输出样例解释1】
如图是满足样例的其中一种方案，最少要种3棵树。
如图是满足样例的其中一种方案，最少要种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