【题目描述】
村里有n幢房屋，这些屋子的排列在一条直线上。我们给它们标上1~n。树就种在房子前面的空地上。
同时，村民们向村长提出了m个意见，每个意见都是按如此格式：希望第Li个房子到第Ri个房子的房前至少有Ci棵树。
因为每个房屋前的空地面积有限，所以每个房屋前最多只能种Ki棵树。
村长希望在满足村民全部要求的同时，种最少的树以节约资金，请你帮助村长。
【输入描述】
输入共三行。
第1行，包含两个整数n、m；
第2行，有n个整数Ki；
第3行到m+1行，每行三个整数Li、Ri、Ci。
【输出描述】
输出一个整数表示在满足村民全部要求的情况下最少要种的树，村民提的要求是可以全部满足的。
【样例输入】
4 3
3 2 4 1
1 2 4
2 3 5
2 4 6
【样例输出】
8
【数据范围及提示】
对于30%的数据，0 < n ≤ 100，0 < m ≤ 100，Ki = 1；
对于50%的数据，0 < n ≤ 2000，0 < m ≤ 5000，0 < Ki ≤ 100；
对于70%的数据，0 < n ≤ 50000，0 < m ≤ 100000，0 < Ki ≤ 1000；
对于100%的数据，0 < n ≤ 500000，0 < m ≤ 500000，0 < Ki ≤ 5000。