Description

Johnny founded Bytecomp, a company that provides cloud computing services. Such companies usually own many fast computers on which customers can run computations.

Johnny has not bought any machines yet. He went to a computer store and received a list of all $n$ available computers. Each computer can be described by three attributes: the number of processor cores $c_i$, the clock frequency $f_i$, and the price $v_i$. Such a computer contains $c_i$ independent cores, so they can be assigned to different tasks.

When a customer places an order, she specifies the required number of cores $C_j$ and the minimum clock frequency $F_j$. The order also contains the price $V_j$ that the customer is willing to pay. If the order is accepted, Bytecomp needs to provide the customer with exclusive access to the required computing power. Johnny needs to choose $C_j$ cores (possibly from different computers) whose clock frequencies are at least $F_j$, and these cores cannot be assigned to other orders.

Help Johnny earn as much money as possible: accept an optimal subset of orders, and choose a subset of computers to satisfy all accepted orders. Your goal is to maximize the profit, i.e. the revenue from providing computing power to customers minus the cost of buying computers.

Input Format

The first line of standard input contains an integer $n$, the number of computers available in the store.

The next $n$ lines each describe one computer and contain three space-separated integers $c_i, f_i, v_i$, denoting the number of cores, the clock frequency, and the price.

The next line contains an integer $m$, the number of customer orders.

The next $m$ lines each describe one order and contain three space-separated integers $C_j, F_j, V_j$, denoting the required number of cores, the minimum allowed clock frequency, and the budget.

Output Format

The only line of standard output contains one integer, the maximum profit that can be obtained.

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

350

Hint

Sample Explanation

There are four available computers and three orders.

The best plan is to buy two 4-core computers with prices $700$ and $750$ (total $1450$), and then accept the first two orders to get revenue $300+1500=1800$.

We obtain four cores with clock frequency $2000$, and four cores with clock frequency $2200$. We can assign six of them to the second order (which requires clock frequency $1900$), then assign one to the first order (which requires clock frequency $1500$), and leave the remaining core unused, which is allowed.

The total profit is $1800-1450=350$.

Constraints

For $100\%$ of the data, $1\le n,m\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$.

All testdata are divided into several subtasks with additional constraints, and each subtask contains several test points.

Translated by ChatGPT 5