题目描述
战线可以看作一个长度为 n 的序列,现在需要在这个序列上建塔来防守敌兵,在序列第 i 号位置上建一座塔有 ci 的花费,且一个位置可以建任意多的塔,费用累加计算。有 m 个区间 [l1,r1],[l2,r2],⋯,[lm,rm],在第 i 个区间的范围内要建至少 di 座塔。求最少花费。
输入格式
第一行为两个数 n,m。接下来一行,有 n 个数,描述 c 数组。接下来 m 行,每行三个数 li,ri,di,描述一个区间。
输出格式
仅包含一行,一个数,为最少花费。
5 3
1 5 6 3 4
2 3 1
1 5 4
3 5 2
11
样例说明
位置 1 建 2 个塔,位置 3 建一个塔,位置 4 建一个塔。花费 1×2+6+3=11。
数据规模与约定
对于 20% 的数据,n≤20,m≤20。
对于 50% 的数据(包括上部分的数据),di 全部为 1。
对于 70% 的数据(包括上部分的数据),n≤100,m≤103。
对于 100% 的数据,n≤1000,m≤104,1≤li≤ri≤n,其余数据均≤104。