单点时限: 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)$。
测试数据保证答案一定有上界。
输出最多能得到的太阳能。
1 5 5 3 5 3 5 2 4 5 3 2 5 3 2 4 5 0 2 1 3 5 3
20
样例最优方案为：$1$ 到 $n$ 每幢楼的高度为 $0, 1, 1, 4, 4$。