Johnny thành lập Bytecomp, một công ty cung cấp năng lực tính toán trên đám mây. Những công ty như vậy thường có nhiều máy tính mạnh để chạy các tác vụ của khách hàng.

Hiện Johnny chưa mua máy nào. Cửa hàng cung cấp \(n\) máy tính. Mỗi máy có \(c_i\) lõi xử lý, tốc độ xung nhịp \(f_i\) và giá \(v_i\). Các lõi của cùng một máy hoạt động độc lập nên có thể được phân cho các tác vụ khác nhau.

Mỗi đơn đặt hàng của khách hàng gồm số lõi cần dùng \(C_j\), tốc độ xung nhịp tối thiểu \(F_j\) và khoản tiền khách hàng trả \(V_j\). Nếu nhận đơn, Johnny phải cung cấp đúng \(C_j\) lõi, có thể lấy từ nhiều máy khác nhau; mỗi lõi được cấp phải có tốc độ xung nhịp ít nhất \(F_j\) và không được cấp cho đơn hàng nào khác.

Hãy chọn các máy cần mua và các đơn hàng cần nhận sao cho mọi đơn được đáp ứng. Tối đa hóa lợi nhuận, bằng tổng tiền thu được từ các đơn hàng trừ tổng giá mua máy.

Dữ liệu vào

Dòng đầu chứa số nguyên \(n\) (\(1\le n\le2000\)), là số máy có thể mua.

Mỗi dòng trong \(n\) dòng tiếp theo chứa ba số nguyên \(c_i,f_i,v_i\) (\(1\le c_i\le50\), \(1\le f_i\le10^9\), \(1\le v_i\le10^9\)), lần lượt là số lõi, tốc độ xung nhịp và giá của máy thứ \(i\).

Dòng tiếp theo chứa số nguyên \(m\) (\(1\le m\le2000\)), là số đơn hàng.

Mỗi dòng trong \(m\) dòng tiếp theo chứa ba số nguyên \(C_j,F_j,V_j\) (\(1\le C_j\le50\), \(1\le F_j\le10^9\), \(1\le V_j\le10^9\)), lần lượt là số lõi cần dùng, tốc độ xung nhịp tối thiểu và khoản tiền của đơn hàng thứ \(j\).

Dữ liệu ra

In một số nguyên duy nhất là lợi nhuận lớn nhất có thể đạt được.

Ví dụ

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

350

Giải thích

Có thể mua hai máy lần lượt giá \(700\) và \(750\), thu tổng cộng \(1800\) từ hai đơn hàng đầu. Bốn lõi của máy thứ nhất có tốc độ \(2200\), bốn lõi của máy thứ hai có tốc độ \(2000\). Có thể cấp sáu lõi cho đơn thứ hai và một lõi cho đơn thứ nhất; một lõi còn lại không cần sử dụng. Lợi nhuận là \(1800-1450=350\).

Phân nhóm

1. \(18\) điểm: \(n\le15\).
2. \(18\) điểm: \(m\le15\).
3. \(18\) điểm: \(n,m\le250\) và \(c_i=C_j=1\) với mọi máy, đơn hàng.
4. \(18\) điểm: \(f_i=F_j=1\) với mọi máy, đơn hàng.
5. \(18\) điểm: \(v_i=V_j=1\) với mọi máy, đơn hàng.
6. \(10\) điểm: Không có ràng buộc bổ sung.