Le cuisinier Bitaro participe à un concours de cuisine. Dans ce concours, chaque participant doit préparer deux plats : IOI Donburi et JOI Curry.

La préparation de IOI Donburi comporte $N$ étapes. La $i$-ème étape ($1 \le i \le N$) prend exactement $A_i$ minutes. Au départ, il peut uniquement effectuer la première étape. Pour effectuer la $i$-ème étape ($2 \le i \le N$), il doit avoir terminé la $(i-1)$-ème étape.

La préparation de JOI Curry comporte $M$ étapes. La $j$-ème étape ($1 \le j \le M$) prend exactement $B_j$ minutes. Au départ, il peut uniquement effectuer la première étape. Pour effectuer la $j$-ème étape ($2 \le j \le M$), il doit avoir terminé la $(j-1)$-ème étape.

Les étapes demandent de la concentration : lorsqu'il commence une étape, il ne peut effectuer aucune autre étape avant de l'avoir terminée. Entre deux étapes, il peut passer d'un plat à l'autre. Une fois le concours commencé, il ne peut prendre aucune pause avant d'avoir terminé les deux plats.

Dans ce concours, les participants reçoivent des points artistiques selon les règles suivantes.

• S'il termine la $i$-ème étape ($1 \le i \le N$) de la préparation de IOI Donburi au plus tard $S_i$ minutes après le début du concours, il reçoit $P_i$ points. La valeur de $P_i$ peut être négative.
• S'il termine la $j$-ème étape ($1 \le j \le M$) de la préparation de JOI Curry au plus tard $T_j$ minutes après le début du concours, il reçoit $Q_j$ points. La valeur de $Q_j$ peut être négative.

Bitaro souhaite maximiser son total de points artistiques.

Écrivez un programme qui, étant donnés le nombre d'étapes de préparation, leur durée et les informations sur les points artistiques, calcule le total maximal de points artistiques que Bitaro peut obtenir.

Entrée

Lisez les données suivantes sur l'entrée standard. Toutes les valeurs de l'entrée sont des entiers.

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

Sortie

Écrivez une ligne sur la sortie standard. Elle doit contenir le total maximal de points artistiques que Bitaro peut obtenir.

Contraintes

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

Sous-tâches

1. (5 points) $N \le 200\,000$, $M \le 200\,000$, $S_1 = \cdots = S_N = T_1 = \cdots = T_M$.
2. (3 points) $N \le 12$, $M \le 12$, $P_i = 1$ ($1 \le i \le N$), $Q_j = 1$ ($1 \le j \le M$).
3. (7 points) $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 points) $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 points) $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 points) $1 \le P_i$ ($1 \le i \le N$), $1 \le Q_j$ ($1 \le j \le M$).
7. (17 points) $N \le 200\,000$, $M \le 200\,000$.
8. (9 points) Aucune contrainte supplémentaire.

Exemples

Entrée 1

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

Sortie 1

6

Remarque

Cette entrée respecte les contraintes de la sous-tâche 2.

Pour cette entrée, Bitaro peut, par exemple, effectuer les étapes dans l'ordre suivant :

1. Il effectue la première étape de JOI Curry. Il la termine 3 minutes après le début du concours. Comme cela ne dépasse pas 6 minutes, il gagne 1 point.
2. Il effectue la première étape de IOI Donburi. Il la termine 5 minutes après le début du concours. Comme cela dépasse 1 minute, il ne gagne aucun point artistique.
3. Il effectue la deuxième étape de IOI Donburi. Il la termine 8 minutes après le début du concours. Comme cela ne dépasse pas 8 minutes, il gagne 1 point.
4. Il effectue la deuxième étape de JOI Curry. Il la termine 10 minutes après le début du concours. Comme cela ne dépasse pas 11 minutes, il gagne 1 point.
5. Il effectue la troisième étape de IOI Donburi. Il la termine 12 minutes après le début du concours. Comme cela ne dépasse pas 13 minutes, il gagne 1 point.
6. Il effectue la quatrième étape de IOI Donburi. Il la termine 13 minutes après le début du concours. Comme cela ne dépasse pas 13 minutes, il gagne 1 point.
7. Il effectue la troisième étape de JOI Curry. Il la termine 15 minutes après le début du concours. Comme cela ne dépasse pas 15 minutes, il gagne 1 point.

Son total de points artistiques est alors de 6 points. Il ne peut pas obtenir plus de 6 points ; il faut donc afficher 6.

Entrée 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

Sortie 2

63

Remarque

Cette entrée respecte les contraintes de la sous-tâche 1.

Entrée 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

Sortie 3

99