Sau nhiều năm theo đuổi IOI không thành, bạn quyết định từ bỏ và thành lập một công ty cung cấp các dịch vụ tính toán trên đám mây. Để làm được điều này, trước tiên bạn phải mua một số máy tính mạnh để đáp ứng được nhu cầu của khách hàng. Bạn vào một cửa hàng bán máy tính để tìm mua những chiếc máy tính có cấu hình mạnh. Cửa hàng có n máy tính, máy tính thứ ~i~ với ~1 ≤ i ≤ N~ có số lượng lõi (core) là ~c_i~, tốc độ tính toán ~f_i~ và giá là ~v_i~. Biết ~c_i~ lõi của máy tính là độc lập với nhau nên máy tính có thể thực hiện ~c_i~ công việc đồng thời.

Tuy chưa mua được máy tính nhưng bạn đã có được ~m~ đơn đặt hàng. Đơn đặt hàng thứ ~i~ với ~1 ≤ i ≤ m~ yêu cầu thuê đúng ~C_i~ lõi, mỗi lõi phải có tốc độ tính toán ít nhất là ~F_i~. Nếu bạn chấp nhận đơn đặt hàng này, bạn cần phải chọn ~C_i~ lõi (có thể từ những máy tính khác nhau) có tốc độ tính toán ít nhất là ~F_i~, cho khách hàng thuê và bạn sẽ được trả ~V_i~ tiền. Tất nhiên, một lõi chỉ có thể được thuê bởi nhiều nhất một khách hàng.

Yêu cầu: hãy tìm cách mua máy tính và cách chấp nhận đơn đặt hàng sao cho lợi nhuận là lớn nhất có thể, trong đó lợi nhuận được tính bằng tổng tiền bạn nhận được từ khách hàng trừ đi chi phí mua máy tính.

Input

Dòng đầu tiên chứa số nguyên ~n~ với ~1 ≤ n ≤ 2000~ là số lượng máy tính có thể mua.

Trong ~n~ dòng sau, dòng thứ ~i~ chứa 3 số nguyên ~c_i, f_i, v_i~ với ~1 ≤ c_i ≤ 50, 1 ≤ f_i ≤ 10^9, 1 ≤ v_i ≤ 10^9~.

Dòng tiếp theo chứa số nguyên ~m~ với ~1 ≤ m ≤ 200~ là số lượng đơn đặt hàng.

Trong ~m~ dòng sau, dòng thứ ~i~ chứa 3 số nguyên ~C_i, F_i, V_i~ với ~1 ≤ Ci ≤ 50, 1 ≤ F_i ≤ 10^9, 1 ≤ Vi ≤ 10^9~.

Output

Một dòng chứa lợi nhuận lớn nhất có thể.

Sample input

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

350

Giải thích chiến lược như sauu: mua 2 máy tính, trong đó máy tính thứ 1 và thứ 4, bạn có ~8~ lõi và chi phí mua là: ~700+750=1450~. Chấp nhận 2 đơn đặt hàng đầu tiên, cần cung cấp 7 lõi cho khách hàng, số tiền thu được là: ~300+1500=1800~ nên lợi nhuận là: ~1800-1450 = 350.~ Dễ dàng chứng minh được đây là lợi nhuận tối ưu.

Subtask:

• Subtask 1: ~n ≤ 15~
• Subtask 2: ~m ≤ 15~
• Subtask 3: ~n, m ≤ 250~ và ~c_i = C_j = 1~ với mọi ~i, j~.
• Subtask 4: ~f_i = F_j = 1~ với mọi ~i, j.~
• Subtask 5: ~v_i = V_j = 1~ với mọi ~i, j.~ Subtask 6: Không có ràng buộc gì thêm