Kucharz Bitaro bierze udział w konkursie kulinarnym. W tym konkursie uczestnik musi przygotować dwie potrawy: IOI Donburi i JOI Curry.

Przygotowanie IOI Donburi składa się z $N$ etapów. Etap $i$ ($1 \le i \le N$) zajmuje dokładnie $A_i$ minut. Początkowo Bitaro może wykonać tylko pierwszy etap. Aby wykonać etap $i$ ($2 \le i \le N$), musi zakończyć etap $i-1$.

Przygotowanie JOI Curry składa się z $M$ etapów. Etap $j$ ($1 \le j \le M$) zajmuje dokładnie $B_j$ minut. Początkowo Bitaro może wykonać tylko pierwszy etap. Aby wykonać etap $j$ ($2 \le j \le M$), musi zakończyć etap $j-1$.

Etapy wymagają skupienia, więc po rozpoczęciu etapu Bitaro nie może wykonywać innych etapów, dopóki go nie zakończy. Między etapami może przechodzić od jednej potrawy do drugiej. Od rozpoczęcia konkursu aż do ukończenia obu potraw nie może robić przerw.

W tym konkursie uczestnik otrzymuje punkty za artyzm według następujących zasad.

• Jeśli zakończy etap $i$ ($1 \le i \le N$) przygotowania IOI Donburi w ciągu $S_i$ minut od rozpoczęcia konkursu, otrzymuje $P_i$ punktów. Wartość $P_i$ może być ujemna.
• Jeśli zakończy etap $j$ ($1 \le j \le M$) przygotowania JOI Curry w ciągu $T_j$ minut od rozpoczęcia konkursu, otrzymuje $Q_j$ punktów. Wartość $Q_j$ może być ujemna.

Bitaro chce zmaksymalizować łączną liczbę punktów za artyzm.

Napisz program, który na podstawie liczby etapów przygotowania potraw, czasu ich trwania oraz informacji o punktach za artyzm obliczy maksymalną łączną liczbę punktów za artyzm, jaką może uzyskać Bitaro.

Wejście

Wczytaj następujące dane ze standardowego wejścia. Wszystkie wartości w danych wejściowych są liczbami całkowitymi.

$$ \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} $$

Wyjście

Wypisz jeden wiersz na standardowe wyjście. Powinien on zawierać maksymalną łączną liczbę punktów za artyzm, jaką może uzyskać Bitaro.

Ograniczenia

• $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$).

Podzadania

1. (5 punktów) $N \le 200\,000$, $M \le 200\,000$, $S_1 = \cdots = S_N = T_1 = \cdots = T_M$.
2. (3 punkty) $N \le 12$, $M \le 12$, $P_i=1$ ($1 \le i \le N$), $Q_j=1$ ($1 \le j \le M$).
3. (7 punktów) $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 punktów) $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 punktów) $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 punktów) $1 \le P_i$ ($1 \le i \le N$), $1 \le Q_j$ ($1 \le j \le M$).
7. (17 punktów) $N \le 200\,000$, $M \le 200\,000$.
8. (9 punktów) Brak dodatkowych ograniczeń.

Przykład

Wejście 1

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

Wyjście 1

6

Uwagi

Ten przykład spełnia ograniczenia podzadania 2.

W tym przykładzie Bitaro może na przykład wykonywać etapy przygotowania potraw w następujący sposób:

1. Wykonuje pierwszy etap JOI Curry. Kończy go po 3 minutach od rozpoczęcia konkursu. Ponieważ mieści się to w limicie 6 minut, otrzymuje 1 punkt.
2. Wykonuje pierwszy etap IOI Donburi. Kończy go po 5 minutach od rozpoczęcia konkursu. Ponieważ nie mieści się to w limicie 1 minuty, nie otrzymuje punktów za artyzm.
3. Wykonuje drugi etap IOI Donburi. Kończy go po 8 minutach od rozpoczęcia konkursu. Ponieważ mieści się to w limicie 8 minut, otrzymuje 1 punkt.
4. Wykonuje drugi etap JOI Curry. Kończy go po 10 minutach od rozpoczęcia konkursu. Ponieważ mieści się to w limicie 11 minut, otrzymuje 1 punkt.
5. Wykonuje trzeci etap IOI Donburi. Kończy go po 12 minutach od rozpoczęcia konkursu. Ponieważ mieści się to w limicie 13 minut, otrzymuje 1 punkt.
6. Wykonuje czwarty etap IOI Donburi. Kończy go po 13 minutach od rozpoczęcia konkursu. Ponieważ mieści się to w limicie 13 minut, otrzymuje 1 punkt.
7. Wykonuje trzeci etap JOI Curry. Kończy go po 15 minutach od rozpoczęcia konkursu. Ponieważ mieści się to w limicie 15 minut, otrzymuje 1 punkt.

Łączna liczba punktów za artyzm wynosi tu 6. Nie można uzyskać więcej niż 6 punktów, więc należy wypisać 6.

Wejście 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

Wyjście 2

63

Uwagi

Ten przykład spełnia ograniczenia podzadania 1.

Wejście 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

Wyjście 3

99