Cloud computing

Time limit2sMemory limit512 MB

Summary

Choose a set of orders and a set of computers to buy so every accepted order gets enough cores at its minimum clock rate, maximizing payments minus computer costs.

Level: Hard9 of 10
Topics: Dynamic programming, Greedy, Sorting, Combinatorics
Solved: No attempts yet

Problem

Johnny is founding Bytecomp, a company that offers computing power in the cloud. Companies with this profile usually have many fast computers on which customers' computations can be performed.

Johnny has not bought any machines yet. He went to a computer shop and received a list of all $n$ computers available there. Each computer is described by the number of processor cores $c_i$ , the clock rate $f_i$ , and the price $v_i$ . Such a computer has $c_i$ separate cores that do not interfere with each other, so they can be assigned to different tasks.

When a customer places an order for resources, she specifies the required number of cores $C_j$ and the minimum clock rate $F_j$ . The order also includes the price $V_j$ the customer is willing to pay in return. If the order is accepted, Bytecomp must provide exclusive access to the computing power the customer requires. Johnny has to choose $C_j$ cores, possibly from different computers, each with a clock rate of at least $F_j$ . Those cores cannot be assigned to any other order.

Help Johnny earn as much as possible. He chooses an optimal subset of orders to accept and a subset of computers to buy from the shop so that all accepted orders are satisfied. The goal is to maximize the total profit, the earnings from providing computing power to customers minus the cost of buying the computers.

Input

The first line of the standard input contains an integer $n$ (1 ≤ n ≤ 2000), the number of computers available at the shop. Each of the next $n$ lines describes one computer with 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), the number of cores, the clock rate, and the price.

The next line contains an integer $m$ (1 ≤ m ≤ 2000), the number of orders. Each of the next $m$ lines describes one order with 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), the number of cores needed, the minimum clock rate, and the amount the customer will pay.

Output

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

Examples1

Example 1

Input

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

Expected output