Đầu bếp Bitaro tham gia một cuộc thi nấu ăn. Anh phải hoàn thành hai món: cơm tô IOI và cà ri JOI.

Món cơm tô IOI gồm \(N\) bước. Bước thứ \(i\) mất đúng \(A_i\) phút. Ban đầu chỉ có thể thực hiện bước thứ nhất; muốn thực hiện bước thứ \(i\ge2\), phải hoàn thành bước thứ \(i-1\) trước.

Món cà ri JOI gồm \(M\) bước. Bước thứ \(j\) mất đúng \(B_j\) phút. Các bước của món này cũng phải thực hiện theo thứ tự từ \(1\) đến \(M\).

Mỗi bước đòi hỏi sự tập trung: một khi bắt đầu một bước, Bitaro không thể làm bước khác trước khi hoàn thành bước đó. Anh có thể đổi món giữa hai bước. Kể từ khi cuộc thi bắt đầu, anh không được nghỉ cho đến khi hoàn thành cả hai món.

Điểm nghệ thuật được tính như sau:

• Nếu hoàn thành bước thứ \(i\) của món cơm tô IOI trong vòng \(S_i\) phút kể từ lúc bắt đầu cuộc thi, Bitaro nhận \(P_i\) điểm. \(P_i\) có thể âm.
• Nếu hoàn thành bước thứ \(j\) của món cà ri JOI trong vòng \(T_j\) phút kể từ lúc bắt đầu cuộc thi, Bitaro nhận \(Q_j\) điểm. \(Q_j\) có thể âm.

Hoàn thành đúng thời hạn vẫn được tính điểm; nếu hoàn thành muộn hơn thời hạn, bước đó không đem lại điểm. Hãy tìm tổng điểm nghệ thuật lớn nhất Bitaro có thể đạt được.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

N M
A_1 S_1 P_1
...
A_N S_N P_N
B_1 T_1 Q_1
...
B_M T_M Q_M

Tất cả dữ liệu vào là số nguyên.

Dữ liệu ra

Ghi một dòng chứa tổng điểm nghệ thuật lớn nhất có thể đạt được.

Ràng buộc

• \(1\le N,M\le1\,000\,000\).
• \(1\le A_i\le10^9\) với \(1\le i\le N\).
• \(1\le B_j\le10^9\) với \(1\le j\le M\).
• \(1\le S_i\le2\times10^{15}\) với \(1\le i\le N\).
• \(1\le T_j\le2\times10^{15}\) với \(1\le j\le M\).
• \(-10^9\le P_i\le10^9\) với \(1\le i\le N\).
• \(-10^9\le Q_j\le10^9\) với \(1\le j\le M\).

Phân nhóm

1. (5 điểm) \(N,M\le200\,000\) và \(S_1=\cdots=S_N=T_1=\cdots=T_M\).
2. (3 điểm) \(N,M\le12\) và \(P_i=Q_j=1\) với mọi \(i,j\).
3. (7 điểm) \(N,M\le2000\) và \(P_i=Q_j=1\) với mọi \(i,j\).
4. (39 điểm) \(N,M\le200\,000\) và \(P_i=Q_j=1\) với mọi \(i,j\).
5. (11 điểm) \(N,M\le200\,000\), \(P_i\ge1\) và \(Q_j\ge1\) với mọi \(i,j\).
6. (9 điểm) \(P_i\ge1\) và \(Q_j\ge1\) với mọi \(i,j\).
7. (17 điểm) \(N,M\le200\,000\).
8. (9 điểm) Không có ràng buộc bổ sung.

Ví dụ

4 3
2 1 1
3 8 1
2 13 1
1 13 1
3 6 1
2 11 1
2 15 1

6

5 7
16 73 16
17 73 10
20 73 1
14 73 16
18 73 10
3 73 2
10 73 7
16 73 19
12 73 4
15 73 15
20 73 14
15 73 8

63

9 11
86 565 58
41 469 -95
73 679 28
91 585 -78
17 513 -63
48 878 -66
66 901 59
72 983 -70
68 1432 11
42 386 -87
36 895 57
100 164 10
96 812 -6
23 961 -66
54 193 51
37 709 82
62 148 -36
28 853 22
15 44 53
77 660 -19

99

Nguồn

JOI 2018/2019 Spring Training Camp, ngày 2. Đề gốc tiếng Anh, do Japanese Committee for the International Olympiad in Informatics công bố. Bản dịch tiếng Việt theo CC BY-SA 4.0.