单点时限: 2.0 sec
内存限制: 256 MB
施工队准备从左到右连续建造 n 座大楼编号为 1 到 n，第 i 幢大楼的高度为 hi。h0=0 表示 n 座大楼前的空地。
为了使每幢大楼都能吸收到太阳光来发电，需要满足 hi≥hi−1。
因为每幢大楼的太阳光吸收能力不同，所以每幢楼实际能得到的太阳能为 (hi−hi−1)⋅vi。
另外为了美观考虑，提出了 m 个限制条件，每一个条件是个 3 元组 (l,r,delta) 表示要满足 hr−hl≤delta。
现在给出 v，以及 m 个限制条件，要求如何设计每幢楼的高度使得总太阳能最大。
第一行是 case 数 T。
每一个 case 首先会有 n (1≤n≤200), m (1≤m≤4000)。接下来一行会有 n 个数表示 vi (1≤vi≤100)。然后是 m 组限制条件 l,r,delta (0≤l<r≤n,0≤delta≤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。