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 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 specified 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 different tasks.

When a customer makes an order for resources, she specifies 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 different 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 profit, that is, the difference between earnings for providing computing power to customers and the cost of buying the computers.

Input

The first line of the standard input contains an integer ~n~ ~(1 \le n \le 2\,000)~, 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 \le c_i \le 50, 1 \le f_i \le 10^9, 1 \le v_i \le 10^9)~ which represent the number of cores, the clock rate, and the price, respectively.

The next line contains an integer ~m~ ~(1 \le m \le 2\,000)~, 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 \le C_j \le 50, 1 \le F_j \le 10^9, 1 \le V_j \le 10^9)~ which represent the number of cores needed, the minimum allowed clock rate, and the customer's budget, respectively.

Output

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

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.

Subtask	Constraints	Points
~1~	~n \le 15~	~18~
~2~	~m \le 15~	~18~
~3~	~n,m \le 250, c_i = C_j = 1~	~18~
~4~	~f_i = F_j = 1~	~18~
~5~	~v_i = V_j = 1~	~18~
~6~	no additional constraints	~10~

Sample Input 1

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

Sample Output 1

350

Explanation for Sample Output 1

There are four available computers and three orders. It is optimal to buy two quad-core computers that cost ~700~ and ~750~ (~1450~ in total) and then accept the first two orders to earn ~300+1500 = 1800~ in total. We then have four cores with clock rate ~2000~ and four cores with clock rate ~2200~. We can assign any six of them to the second order (clock rate ~1900~ needed) and one to the first order (clock rate ~1500~ needed). One core will not be used, which is allowed.

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