[CEOI2018] Cloud computing

译自 CEOI2018 Day1 T1. [Cloud Computing](https://ceoi2018.pl/wp-content/uploads/2018/08/clo.pdf)。

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$，表示商店中可用计算机的数量。 接下来 $n$ 行，每行描述一台计算机，包含三个空格隔开的整数 $c_i, f_i, v_i$，分别表示内核数，时钟频率和价格。 接下来一行一个整数 $m$，表示客户的订单数量。 接下来 $m$ 行，每行描述一个订单，包含三个空格隔开的整数 $C_j, F_j, V_j$，分别表示需要的核心数，最低的允许的时钟频率以及预算。

标准输出唯一的一行包含一个整数，表示能够得到的最大利润。

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$。 #### 数据规模与约定 对于 $100\%$ 的数据，$1\le n\le 2\times 10^3,\ 1\le c_i,C_i\le 50,\ 1\le f_i,F_i,v_i,V_i\le 10^9$。 所有测试数据被划分成若干个有附加限制的子任务，每个子任务中包含若干测试点。 | 子任务 | 附加限制 | 分值 | | :--: | :---: | :--: | | $1$ | $n \le 15$ | $18$ | | $2$ | $m \le 15$ | $18$ | | $3$ | $n,m \le 100$，$c_i = C_j = 1$ | $18$ | | $4$ | $f_i = F_j = 1$ | $18$ | | $5$ | $v_i = V_j = 1$ | $18$ | | $6$ | 无附加限制 | $10$ |