P6359 [CEOI 2018] 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 赚尽可能多的钱：接受一个最优的订单子集，选择所有计算机的一个子集来满足所有接受了的订单。你的目标是最大化利润，即为客户提供计算能力的收入与购买计算机的成本之差。

无

无

#### 样例解释 一共有四台可用的计算机和三个订单。 最佳方案是购买两台价格为 $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$ |