#3182. 「CEOI2018」云计算

内存限制:256 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: PinkRabbit

题目描述

译自 CEOI2018 Day1 T1. Cloud Computing


Johnny 成立了 Bytecomp,一个提供云计算能力的公司。这样的公司通常拥有许多快速计算机,客户可以在其上进行计算。

但是 Johnny 还没有购买任何计算机。于是他前往一家计算机商店,收到了包含全部 n 台可用的计算机的清单。
每台计算机都可以用三个属性描述:处理器的核心数量 c_i ,时钟频率 f_i 以及价格 v_i 。每台计算机包含 c_i 个不会互相干扰的核心,所以它们可以被分配给不同的任务。

当客户订购资源时,她会指定所需的核心数 C_j 以及所需的最低时钟频率 F_j ,订单还包含客户愿意支付的价格 V_j
如果接受了一份订单,Bytecomp 需要提供对客户所需的算力的专用访问权。Johnny 需要选择 C_j 个核心(可能来自不同的计算机),且它们的时钟频率至少为 F_j ,这些核心不能被分配给其它订单。

请你帮助 Johnny 赚取尽可能多的利润:接受一部分客户订单,并购买商店中的一部分计算机,以满足所有接受了的订单的需求。
你的目标是最大化总利润,即为客户提供算力的收入与购买计算机的成本之间的差值。

输入格式

第一行一个整数 n 1 \le n \le 2000 ),表示商店中可用的计算机的台数。
接下来 n 行,每行描述一台计算机,包含三个整数 c_i, f_i, v_i 1 \le c_i \le 50 1 \le f_i \le 10^9 1 \le v_i \le 10^9 ),分别表示核心数,时钟频率和价格。

接下来一行一个整数 m 1 \le m \le 2000 ),表示客户的订单总数。
接下来 m 行,每行描述一个订单,包含三个整数 C_j, F_j, V_j 1 \le C_j \le 50 1 \le F_j \le 10^9 1 \le V_j \le 10^9 ),分别表示需要的核心数,最低时钟频率以及预算。

输出格式

仅一行一个整数,表示能够获得的最大总利润。

样例

样例输入

4
4 2200 700
2 1800 10
20 2550 9999
4 2000 750
3
1 1500 300
6 1900 1500
3 2400 4550

样例输出

350

样例解释

有四台可用的计算机和三个订单。
最佳方案是购买两台价格为 700 750 (总计 1450 )的四核计算机,然后接受前两个订单以获得 300 + 1500 = 1800 的收益。
我们获得了四个时钟频率为 2000 的核心,和四个时钟频率为 2200 的核心。可以将其中六个分配给第一个订单(需要 1900 的时钟频率),再将其中一个分配给第二个订单(需要 1500 的时钟频率),剩下一个核心不使用,这是允许的。

则总利润为 1800 - 1450 = 350

数据范围与提示

子任务 约束 分值
1 n \le 15 18
2 m \le 15
3 n, m \le 100 c_i = C_j = 1
4 f_i = F_j = 1
5 v_i = V_j = 1
6 无特殊约束 10