Maximizing Profit for Bytecomp Orders

Johnny founded Bytecomp, a cloud computing company. He receives a list of \(n\) available computers. Each computer is described by three parameters: the number of cores \(c_i\), the clock frequency \(f_i\) and the price \(v_i\). When a customer places an order, she specifies the required number of cores \(C_j\), the minimum required clock frequency \(F_j\) and the price she is willing to pay \(V_j\). If Bytecomp accepts an order, it must allocate \(C_j\) cores (possibly from different computers) from the purchased computers that have clock frequencies at least \(F_j\); note that one core can only be assigned to one order.

Your task is to choose a subset of orders to accept and a subset of computers to purchase such that all accepted orders are fulfilled, and to maximize the profit defined as the total revenue (sum of \(V_j\) for accepted orders) minus the total cost (sum of \(v_i\) for purchased computers). If no selection yields a positive profit, output 0.

Note: It is guaranteed that the input sizes are small enough so that a solution using brute force over all subsets is feasible.

inputFormat

The first line contains an integer \(n\) (the number of computers). Each of the next \(n\) lines contains three integers \(c_i\), \(f_i\) and \(v_i\), describing a computer.

The next line contains an integer \(m\) (the number of orders). Each of the following \(m\) lines contains three integers \(C_j\), \(F_j\) and \(V_j\), describing an order.

outputFormat

Output a single integer, the maximum profit (total revenue from accepted orders minus total cost of purchased computers) that can be achieved. If no profitable solution exists, output 0.

sample

2
4 3 10
3 2 5
2
3 2 20
4 3 25

30