Koch Bitaro nimmt an einem Kochwettbewerb teil. Bei diesem Wettbewerb muss ein Teilnehmer zwei Gerichte zubereiten: IOI Donburi und JOI Curry.

Die Zubereitung von IOI Donburi besteht aus $N$ Schritten. Der $i$-te Schritt ($1 \le i \le N$) dauert genau $A_i$ Minuten. Anfangs kann er nur den ersten Schritt ausführen. Um den $i$-ten Schritt ($2 \le i \le N$) auszuführen, muss er den $(i-1)$-ten Schritt abgeschlossen haben.

Die Zubereitung von JOI Curry besteht aus $M$ Schritten. Der $j$-te Schritt ($1 \le j \le M$) dauert genau $B_j$ Minuten. Anfangs kann er nur den ersten Schritt ausführen. Um den $j$-ten Schritt ($2 \le j \le M$) auszuführen, muss er den $(j-1)$-ten Schritt abgeschlossen haben.

Die Schritte erfordern Konzentration. Sobald er mit einem Schritt beginnt, kann er daher bis zu dessen Abschluss keine anderen Schritte ausführen. Zwischen den Schritten darf er von einem Gericht zum anderen wechseln. Sobald der Wettbewerb begonnen hat, darf er keine Pause machen, bis er beide Gerichte fertiggestellt hat.

Bei diesem Wettbewerb erhält ein Teilnehmer außerdem wie folgt Punkte für den künstlerischen Wert.

• Wenn er den $i$-ten Schritt ($1 \le i \le N$) der Zubereitung von IOI Donburi innerhalb von $S_i$ Minuten nach Beginn des Wettbewerbs abschließt, erhält er $P_i$ Punkte. Dabei kann $P_i$ negativ sein.
• Wenn er den $j$-ten Schritt ($1 \le j \le M$) der Zubereitung von JOI Curry innerhalb von $T_j$ Minuten nach Beginn des Wettbewerbs abschließt, erhält er $Q_j$ Punkte. Dabei kann $Q_j$ negativ sein.

Bitaro möchte seine Gesamtpunktzahl für den künstlerischen Wert maximieren.

Schreibe ein Programm, das anhand der Anzahl der Zubereitungsschritte, ihrer Dauer und der Angaben zu den Punkten für den künstlerischen Wert die maximale Gesamtpunktzahl berechnet, die Bitaro erreichen kann.

Eingabe

Lies die folgenden Daten aus der Standardeingabe. Alle Werte in der Eingabe sind ganze Zahlen.

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

Ausgabe

Gib eine Zeile auf der Standardausgabe aus. Die Ausgabe soll die maximale Gesamtpunktzahl für den künstlerischen Wert enthalten, die Bitaro erreichen kann.

Beschränkungen

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

Teilaufgaben

1. (5 Punkte) $N \le 200\,000$, $M \le 200\,000$, $S_1 = \cdots = S_N = T_1 = \cdots = T_M$.
2. (3 Punkte) $N \le 12$, $M \le 12$, $P_i = 1$ ($1 \le i \le N$), $Q_j = 1$ ($1 \le j \le M$).
3. (7 Punkte) $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 Punkte) $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 Punkte) $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 Punkte) $1 \le P_i$ ($1 \le i \le N$), $1 \le Q_j$ ($1 \le j \le M$).
7. (17 Punkte) $N \le 200\,000$, $M \le 200\,000$.
8. (9 Punkte) Keine zusätzlichen Beschränkungen.

Beispiele

Eingabe 1

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

Ausgabe 1

6

Hinweis

Diese Beispieleingabe erfüllt die Beschränkungen von Teilaufgabe 2.

Bei dieser Beispieleingabe kann Bitaro die Zubereitungsschritte beispielsweise wie folgt ausführen:

1. Er führt den 1. Schritt von JOI Curry aus. Er schließt ihn 3 Minuten nach Beginn des Wettbewerbs ab. Da dies innerhalb von 6 Minuten geschieht, erhält er 1 Punkt.
2. Er führt den 1. Schritt von IOI Donburi aus. Er schließt ihn 5 Minuten nach Beginn des Wettbewerbs ab. Da dies nicht innerhalb von 1 Minute geschieht, erhält er keine Punkte für den künstlerischen Wert.
3. Er führt den 2. Schritt von IOI Donburi aus. Er schließt ihn 8 Minuten nach Beginn des Wettbewerbs ab. Da dies innerhalb von 8 Minuten geschieht, erhält er 1 Punkt.
4. Er führt den 2. Schritt von JOI Curry aus. Er schließt ihn 10 Minuten nach Beginn des Wettbewerbs ab. Da dies innerhalb von 11 Minuten geschieht, erhält er 1 Punkt.
5. Er führt den 3. Schritt von IOI Donburi aus. Er schließt ihn 12 Minuten nach Beginn des Wettbewerbs ab. Da dies innerhalb von 13 Minuten geschieht, erhält er 1 Punkt.
6. Er führt den 4. Schritt von IOI Donburi aus. Er schließt ihn 13 Minuten nach Beginn des Wettbewerbs ab. Da dies innerhalb von 13 Minuten geschieht, erhält er 1 Punkt.
7. Er führt den 3. Schritt von JOI Curry aus. Er schließt ihn 15 Minuten nach Beginn des Wettbewerbs ab. Da dies innerhalb von 15 Minuten geschieht, erhält er 1 Punkt.

Hier beträgt die Gesamtpunktzahl für den künstlerischen Wert 6 Punkte. Er kann nicht mehr als 6 Punkte erreichen, gib daher 6 aus.

Eingabe 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

Ausgabe 2

63

Hinweis

Diese Beispieleingabe erfüllt die Beschränkungen von Teilaufgabe 1.

Eingabe 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

Ausgabe 3

99