הטבח Bitaro משתתף בתחרות בישול. בתחרות זו על כל משתתף להכין שתי מנות: IOI Donburi ו־JOI Curry.

תהליך ההכנה של IOI Donburi מורכב מ־$N$ שלבים. השלב ה־$i$ ($1 \le i \le N$) נמשך בדיוק $A_i$ דקות. בתחילה הוא יכול לבצע רק את השלב הראשון. כדי לבצע את השלב ה־$i$ ($2 \le i \le N$), עליו לסיים קודם את השלב ה־$(i-1)$.

תהליך ההכנה של JOI Curry מורכב מ־$M$ שלבים. השלב ה־$j$ ($1 \le j \le M$) נמשך בדיוק $B_j$ דקות. בתחילה הוא יכול לבצע רק את השלב הראשון. כדי לבצע את השלב ה־$j$ ($2 \le j \le M$), עליו לסיים קודם את השלב ה־$(j-1)$.

השלבים דורשים ריכוז, ולכן מרגע שהוא מתחיל לבצע שלב, הוא אינו יכול לבצע שלבים אחרים עד שיסיים אותו. בין שלבים הוא רשאי לעבור ממנה אחת לאחרת. מרגע שהתחרות מתחילה, הוא אינו רשאי לנוח עד שיסיים את שתי המנות.

בנוסף, בתחרות זו המשתתפים מקבלים ניקוד אמנותי באופן הבא.

• אם הוא מסיים את השלב ה־$i$ ($1 \le i \le N$) בהכנת IOI Donburi בתוך $S_i$ דקות מתחילת התחרות, הוא מקבל $P_i$ נקודות. הערך של $P_i$ עשוי להיות שלילי.
• אם הוא מסיים את השלב ה־$j$ ($1 \le j \le M$) בהכנת JOI Curry בתוך $T_j$ דקות מתחילת התחרות, הוא מקבל $Q_j$ נקודות. הערך של $Q_j$ עשוי להיות שלילי.

Bitaro רוצה למקסם את סך הניקוד האמנותי שלו.

כתבו תוכנית שמקבלת את מספר שלבי ההכנה, את משך הזמן שלהם ואת המידע על הניקוד האמנותי, ומחשבת את סך הניקוד האמנותי המרבי ש־Bitaro יכול להשיג.

קלט

קראו את הנתונים הבאים מהקלט הסטנדרטי. כל הערכים בקלט הם מספרים שלמים.

$$ \begin{array}{lll} 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} $$

פלט

כתבו שורה אחת לפלט הסטנדרטי. הפלט צריך להכיל את סך הניקוד האמנותי המרבי ש־Bitaro יכול להשיג.

מגבלות

• $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 \times 10^{15}$ ($1 \le i \le N$).
• $1 \le T_j \le 2\,000\,000\,000\,000\,000 = 2 \times 10^{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$).

תתי־משימות

1. (5 נקודות) $N \le 200\,000$, $M \le 200\,000$, $S_1=\cdots=S_N=T_1=\cdots=T_M$.
2. (3 נקודות) $N \le 12$, $M \le 12$, $P_i=1$ ($1 \le i \le N$), $Q_j=1$ ($1 \le j \le M$).
3. (7 נקודות) $N \le 2\,000$, $M \le 2\,000$, $P_i=1$ ($1 \le i \le N$), $Q_j=1$ ($1 \le j \le M$).
4. (39 נקודות) $N \le 200\,000$, $M \le 200\,000$, $P_i=1$ ($1 \le i \le N$), $Q_j=1$ ($1 \le j \le M$).
5. (11 נקודות) $N \le 200\,000$, $M \le 200\,000$, $1 \le P_i$ ($1 \le i \le N$), $1 \le Q_j$ ($1 \le j \le M$).
6. (9 נקודות) $1 \le P_i$ ($1 \le i \le N$), $1 \le Q_j$ ($1 \le j \le M$).
7. (17 נקודות) $N \le 200\,000$, $M \le 200\,000$.
8. (9 נקודות) ללא מגבלות נוספות.

דוגמאות

קלט 1

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

פלט 1

6

הסבר

הקלט לדוגמה זה מקיים את המגבלות של תת־משימה 2.

בקלט לדוגמה זה, Bitaro יכול לבצע את שלבי ההכנה, למשל, כך:

1. הוא מבצע את השלב הראשון של JOI Curry. הוא מסיים אותו 3 דקות לאחר תחילת התחרות. מכיוון שזמן זה נמצא בתוך 6 דקות, הוא מקבל נקודה אחת.
2. הוא מבצע את השלב הראשון של IOI Donburi. הוא מסיים אותו 5 דקות לאחר תחילת התחרות. מכיוון שזמן זה אינו בתוך דקה אחת, הוא אינו מקבל ניקוד אמנותי.
3. הוא מבצע את השלב השני של IOI Donburi. הוא מסיים אותו 8 דקות לאחר תחילת התחרות. מכיוון שזמן זה נמצא בתוך 8 דקות, הוא מקבל נקודה אחת.
4. הוא מבצע את השלב השני של JOI Curry. הוא מסיים אותו 10 דקות לאחר תחילת התחרות. מכיוון שזמן זה נמצא בתוך 11 דקות, הוא מקבל נקודה אחת.
5. הוא מבצע את השלב השלישי של IOI Donburi. הוא מסיים אותו 12 דקות לאחר תחילת התחרות. מכיוון שזמן זה נמצא בתוך 13 דקות, הוא מקבל נקודה אחת.
6. הוא מבצע את השלב הרביעי של IOI Donburi. הוא מסיים אותו 13 דקות לאחר תחילת התחרות. מכיוון שזמן זה נמצא בתוך 13 דקות, הוא מקבל נקודה אחת.
7. הוא מבצע את השלב השלישי של JOI Curry. הוא מסיים אותו 15 דקות לאחר תחילת התחרות. מכיוון שזמן זה נמצא בתוך 15 דקות, הוא מקבל נקודה אחת.

סך הניקוד האמנותי כאן הוא 6 נקודות. הוא אינו יכול להשיג יותר מ־6 נקודות, ולכן יש להדפיס 6.

קלט 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

פלט 2

63

הסבר

הקלט לדוגמה זה מקיים את המגבלות של תת־משימה 1.

קלט 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

פלט 3

99