种树

题目描述

为了绿化乡村，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