3230. Buildings

单点时限: 2.0 sec

内存限制: 256 MB

施工队准备从左到右连续建造 $n$ 座大楼编号为 $1$ 到 $n$,第 $i$ 幢大楼的高度为 $h_i$。$h_0=0$ 表示 $n$ 座大楼前的空地。

为了使每幢大楼都能吸收到太阳光来发电,需要满足 $h_i \geq h_{i-1}$。

因为每幢大楼的太阳光吸收能力不同,所以每幢楼实际能得到的太阳能为 $(h_i - h_{i - 1}) \cdot v_i$。

另外为了美观考虑,提出了 $m$ 个限制条件,每一个条件是个 3 元组 $(l, r, delta)$ 表示要满足 $h_r - h_l \leq delta$。

现在给出 $v$,以及 $m$ 个限制条件,要求如何设计每幢楼的高度使得总太阳能最大。

输入格式

第一行是 case 数 $T$。

每一个 case 首先会有 $n$ $(1 \leq n \leq 200)$, $m$ $(1 \leq m \leq 4000)$。接下来一行会有 $n$ 个数表示 $v_i$ $(1 \leq v_i \leq 100)$。然后是 $m$ 组限制条件 $l, r, delta$ $(0 \leq l < r \leq n, 0 \leq delta \leq 10000)$。

测试数据保证答案一定有上界。

输出格式

输出最多能得到的太阳能。

样例

Input
1
5 5
3 5 3 5 2
4 5 3
2 5 3
2 4 5
0 2 1
3 5 3
Output
20

提示

样例最优方案为:$1$ 到 $n$ 每幢楼的高度为 $0, 1, 1, 4, 4$。

3 人解决,5 人已尝试。

3 份提交通过,共有 16 份提交。

8.5 EMB 奖励。

创建: 3 年,3 月前.

修改: 2 年,11 月前.

最后提交: 2 年,7 月前.

来源: 2017 华东理工上海高校邀请赛

题目标签