[ZJOI2013]防守战线

题目描述

战线可以看作一个长度为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

输出样例 #1

11

说明

【样例说明】 位置1 建2 个塔,位置3 建一个塔,位置4 建一个塔。花费1\*2+6+3=11。 【数据规模】 对于20%的数据,n≤20,m≤20。 对于50%的数据(包括上部分的数据),Di 全部为1。 对于70%的数据(包括上部分的数据),n≤100,m≤1000。 对于100%的数据,n≤1000,m≤10000,1≤Li≤Ri≤n,其余数据均≤10000。