[CEOI2018Day1] Cloud computing

内存限制：256 MB 时间限制：1000 ms

Johnny is founding Bytecomp, a company that oﬀers computing power in the cloud. Companies with this proﬁle usually have many fast computers on which customers’ computations can be made.

Johnny still has not bought any machines. He went to a computer shop and received a list of all $n$ available computers. Every computer is speciﬁed by the number of (processor) cores $c_i$, the clock rate $f_i$, and the price $v_i$. Such a computer contains $c_i$ separate cores that do not interfere with each other, so they can be assigned to diﬀerent tasks.

When a customer makes an order for resources, she speciﬁes the required number of cores $C_j$ and the minimum needed clock rate $F_j$. An order also contains the price $V_j$ that the customer is willing to pay in return. If an order is accepted, Bytecomp needs to provide exclusive access to computing power required by the customer. Johnny needs to choose $C_j$ cores (possibly from diﬀerent computers), each with clock rate at least $F_j$. Those cores cannot be assigned to any other order.

Help Johnny earn as much as possible: choose an optimal subset of orders to accept and a subset of computers from the shop to satisfy all the accepted orders. Your goal is to maximize the total proﬁt, that is, the diﬀerence between earnings for providing computing power to customers and the cost of buying the computers.

The ﬁrst line of the standard input contains an integer $n (1 ≤ n ≤ 2000)$, the number of computers that are available at the shop. Each of next $n$ lines contains a description of one computer. It consists of three space-separated integers $c_i$, $f_i$, and $v_i (1 ≤ c_i ≤ 50, 1 ≤ f_i ≤ 10^9, 1 ≤ v_i ≤ 10^9)$ which represent the number of cores, the clock rate, and the price, respectively.

The next line contains an integer $m (1 ≤ m ≤ 2000)$, the number of orders. Each of next $m$ lines contains a description of one order. It consists of three space-separated integers $C_j$, $F_j$, and $V_j (1 ≤ C_j ≤ 50, 1 ≤ F_j ≤ 10^9, 1 ≤ V_j ≤ 10^9)$ which represent the number of cores needed, the minimum allowed clock rate, and the customer’s budget, respectively.

The only line of the standard output should contain one integer, the maximum total proﬁt that can be achieved.

样例输入 1

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

样例输出 1

Grading

The test set is divided into the following subtasks with additional constraints. Tests in each of the subtasks consist of one or more separate test groups. Each test group may contain one or more test cases.

C1735 [CEOI2018Day1] Cloud computing

题目描述

输入格式

输出

样例

样例输入 1

样例输出 1

提示