bzoj#P3112. [Zjoi2013]防守战线

[Zjoi2013]防守战线

题目描述

战线可以看作一个长度为 nn 的序列,现在需要在这个序列上建塔来防守敌兵,在序列第 ii 号位置上建一座塔有 cic_i 的花费,且一个位置可以建任意多的塔,费用累加计算。有 mm 个区间 [l1,r1],[l2,r2],,[lm,rm][l_1, r_1], [l_2, r_2], \cdots, [l_m, r_m],在第 i 个区间的范围内要建至少 did_i 座塔。求最少花费。

输入格式

第一行为两个数 n,mn, m。接下来一行,有 nn 个数,描述 cc 数组。接下来 mm 行,每行三个数 li,ri,dil _i,r_i,d_i,描述一个区间。

输出格式

仅包含一行,一个数,为最少花费。

5 3
1 5 6 3 4
2 3 1
1 5 4
3 5 2
11

样例说明

位置 1122 个塔,位置 33 建一个塔,位置 44 建一个塔。花费 1×2+6+3=111 \times 2+6+3=11

数据规模与约定

对于 20%20\% 的数据,n20n\le20m20m \le 20

对于 50%50\% 的数据(包括上部分的数据),did_i 全部为 11

对于 70%70\% 的数据(包括上部分的数据),n100m103n\le 100,m\le 10^3

对于 100%100\% 的数据,n1000m1041lirinn\le 1000,m\le 10^4,1\le l_i\le r_i\le n,其余数据均104\le 10^4