Đầu bếp Bitaro đang tham gia một cuộc thi nấu ăn. Trong cuộc thi này, thí sinh phải nấu hai món: IOI Donburi và JOI Curry.

Quá trình nấu IOI Donburi gồm $N$ bước. Bước thứ $i$ ($1\le i\le N$) mất đúng $A_i$ phút. Ban đầu, anh ấy chỉ có thể thực hiện bước đầu tiên. Để thực hiện bước thứ $i$ ($2\le i\le N$), anh ấy phải hoàn thành bước thứ $i-1$.

Quá trình nấu JOI Curry gồm $M$ bước. Bước thứ $j$ ($1\le j\le M$) mất đúng $B_j$ phút. Ban đầu, anh ấy chỉ có thể thực hiện bước đầu tiên. Để thực hiện bước thứ $j$ ($2\le j\le M$), anh ấy phải hoàn thành bước thứ $j-1$.

Các bước đòi hỏi sự tập trung, nên khi bắt đầu thực hiện một bước, anh ấy không thể thực hiện bước khác cho đến khi hoàn thành bước đó. Giữa các bước, anh ấy có thể chuyển từ món này sang món kia. Một khi cuộc thi bắt đầu, anh ấy không được nghỉ cho đến khi hoàn thành cả hai món.

Trong cuộc thi này, thí sinh được chấm điểm nghệ thuật như sau.

• Nếu hoàn thành bước thứ $i$ ($1\le i\le N$) của món IOI Donburi trong vòng $S_i$ phút kể từ khi cuộc thi bắt đầu, anh ấy được $P_i$ điểm. Giá trị $P_i$ có thể âm.
• Nếu hoàn thành bước thứ $j$ ($1\le j\le M$) của món JOI Curry trong vòng $T_j$ phút kể từ khi cuộc thi bắt đầu, anh ấy được $Q_j$ điểm. Giá trị $Q_j$ có thể âm.

Bitaro muốn tối đa hóa tổng điểm nghệ thuật của mình.

Hãy viết chương trình nhận số bước nấu ăn, thời gian thực hiện các bước và thông tin về điểm nghệ thuật, rồi tính tổng điểm nghệ thuật lớn nhất mà Bitaro có thể đạt được.

Dữ liệu vào

Đọc dữ liệu sau từ đầu vào chuẩn. Mọi giá trị trong dữ liệu vào đều là số nguyên.

$$ \begin{array}{l} N\ M\\ A_1\ S_1\ P_1\\ \vdots\\ A_N\ S_N\ P_N\\ B_1\ T_1\ Q_1\\ \vdots\\ B_M\ T_M\ Q_M \end{array} $$

Dữ liệu ra

Ghi một dòng ra đầu ra chuẩn, chứa tổng điểm nghệ thuật lớn nhất mà Bitaro có thể đạt được.

Giới hạn

• $1\le N\le 1\,000\,000$.
• $1\le M\le 1\,000\,000$.
• $1\le A_i\le 1\,000\,000\,000$ ($1\le i\le N$).
• $1\le B_j\le 1\,000\,000\,000$ ($1\le j\le M$).
• $1\le S_i\le 2\,000\,000\,000\,000\,000=2\times10^{15}$ ($1\le i\le N$).
• $1\le T_j\le 2\,000\,000\,000\,000\,000=2\times10^{15}$ ($1\le j\le M$).
• $-1\,000\,000\,000\le P_i\le 1\,000\,000\,000$ ($1\le i\le N$).
• $-1\,000\,000\,000\le Q_j\le 1\,000\,000\,000$ ($1\le j\le M$).

Nhiệm vụ con

1. (5 điểm) $N\le200\,000$, $M\le200\,000$, $S_1=\cdots=S_N=T_1=\cdots=T_M$.
2. (3 điểm) $N\le12$, $M\le12$, $P_i=1$ ($1\le i\le N$), $Q_j=1$ ($1\le j\le M$).
3. (7 điểm) $N\le2\,000$, $M\le2\,000$, $P_i=1$ ($1\le i\le N$), $Q_j=1$ ($1\le j\le M$).
4. (39 điểm) $N\le200\,000$, $M\le200\,000$, $P_i=1$ ($1\le i\le N$), $Q_j=1$ ($1\le j\le M$).
5. (11 điểm) $N\le200\,000$, $M\le200\,000$, $1\le P_i$ ($1\le i\le N$), $1\le Q_j$ ($1\le j\le M$).
6. (9 điểm) $1\le P_i$ ($1\le i\le N$), $1\le Q_j$ ($1\le j\le M$).
7. (17 điểm) $N\le200\,000$, $M\le200\,000$.
8. (9 điểm) Không có giới hạn bổ sung.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

6

Ghi chú

Dữ liệu vào này thỏa mãn các giới hạn của nhiệm vụ con 2.

Trong ví dụ này, Bitaro có thể thực hiện các bước nấu ăn theo cách sau:

1. Anh ấy thực hiện bước thứ nhất của JOI Curry và hoàn thành sau 3 phút kể từ khi cuộc thi bắt đầu. Vì thời điểm này nằm trong vòng 6 phút, anh ấy được 1 điểm.
2. Anh ấy thực hiện bước thứ nhất của IOI Donburi và hoàn thành sau 5 phút kể từ khi cuộc thi bắt đầu. Vì thời điểm này không nằm trong vòng 1 phút, anh ấy không được điểm nghệ thuật nào.
3. Anh ấy thực hiện bước thứ hai của IOI Donburi và hoàn thành sau 8 phút kể từ khi cuộc thi bắt đầu. Vì thời điểm này nằm trong vòng 8 phút, anh ấy được 1 điểm.
4. Anh ấy thực hiện bước thứ hai của JOI Curry và hoàn thành sau 10 phút kể từ khi cuộc thi bắt đầu. Vì thời điểm này nằm trong vòng 11 phút, anh ấy được 1 điểm.
5. Anh ấy thực hiện bước thứ ba của IOI Donburi và hoàn thành sau 12 phút kể từ khi cuộc thi bắt đầu. Vì thời điểm này nằm trong vòng 13 phút, anh ấy được 1 điểm.
6. Anh ấy thực hiện bước thứ tư của IOI Donburi và hoàn thành sau 13 phút kể từ khi cuộc thi bắt đầu. Vì thời điểm này nằm trong vòng 13 phút, anh ấy được 1 điểm.
7. Anh ấy thực hiện bước thứ ba của JOI Curry và hoàn thành sau 15 phút kể từ khi cuộc thi bắt đầu. Vì thời điểm này nằm trong vòng 15 phút, anh ấy được 1 điểm.

Tổng điểm nghệ thuật ở đây là 6 điểm. Anh ấy không thể đạt hơn 6 điểm, nên xuất 6.

Dữ liệu vào 2

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

Dữ liệu ra 2

63

Ghi chú

Dữ liệu vào này thỏa mãn các giới hạn của nhiệm vụ con 1.

Dữ liệu vào 3

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

Dữ liệu ra 3

99