3230. Buildings

单点时限: 2.0 sec

内存限制: 256 MB

施工队准备从左到右连续建造 座大楼编号为 ,第 幢大楼的高度为 表示 座大楼前的空地。

为了使每幢大楼都能吸收到太阳光来发电,需要满足

因为每幢大楼的太阳光吸收能力不同,所以每幢楼实际能得到的太阳能为

另外为了美观考虑,提出了 个限制条件,每一个条件是个 3 元组 表示要满足

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

输入格式

第一行是 case 数

每一个 case 首先会有 , 。接下来一行会有 个数表示 。然后是 组限制条件

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

输出格式

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

样例

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

提示

样例最优方案为: 每幢楼的高度为

3 人解决,5 人已尝试。

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

8.5 EMB 奖励。

创建: 2 年,8 月前.

修改: 2 年,4 月前.

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

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

题目标签