[ZJOI2013]防守战线
题号：NC20512
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

战线可以看作一个长度为 n 的序列，现在需要在这个序列上建塔来防守敌兵，在序列第 i号位置上建一座塔有 Ci 的花费，且一个位置可以建任意多的塔费用累加计算。
有 m个区间[L1, R1], [L2, R2], …, [Lm, Rm]，在第 i 个区间的范围内要建至少 Di座塔。求最少花费。

输入描述:

第一行为两个数n,m。
接下来一行，有 n个数，描述 C数组。
接下来 m行，每行三个数 Li,Ri,Di，描述一个区间。

输出描述:

仅包含一行，一个数，为最少花费。
示例1

输入

复制 
5 3
1 5 6 3 4
2 3 1
1 5 4
3 5 2

输出

复制 
11

备注:

对于20%的数据，。
对于50%的数据（包括上部分的数据），Di全部为1。
对于70%的数据（包括上部分的数据），。
对于100%的数据，，其余数据均。