El cocinero Bitaro participa en un concurso de cocina. En este concurso, cada participante debe preparar dos platos: IOI Donburi y JOI Curry.

La preparación de IOI Donburi consta de $N$ pasos. El paso $i$ ($1 \le i \le N$) dura exactamente $A_i$ minutos. Al principio, solo puede realizar el primer paso. Para realizar el paso $i$ ($2 \le i \le N$), debe haber terminado el paso $i-1$.

La preparación de JOI Curry consta de $M$ pasos. El paso $j$ ($1 \le j \le M$) dura exactamente $B_j$ minutos. Al principio, solo puede realizar el primer paso. Para realizar el paso $j$ ($2 \le j \le M$), debe haber terminado el paso $j-1$.

Los pasos requieren concentración, por lo que, una vez que empieza un paso, no puede realizar ningún otro hasta terminarlo. Entre dos pasos puede cambiar de un plato al otro. Una vez iniciado el concurso, no puede descansar hasta completar los dos platos.

Por cierto, en este concurso se otorgan puntos artísticos a cada participante de la siguiente manera.

• Si termina el paso $i$ ($1 \le i \le N$) de la preparación de IOI Donburi dentro de los primeros $S_i$ minutos desde el inicio del concurso, recibe $P_i$ puntos. El valor de $P_i$ puede ser negativo.
• Si termina el paso $j$ ($1 \le j \le M$) de la preparación de JOI Curry dentro de los primeros $T_j$ minutos desde el inicio del concurso, recibe $Q_j$ puntos. El valor de $Q_j$ puede ser negativo.

Bitaro quiere maximizar su puntuación artística total.

Escribe un programa que, dados el número de pasos de preparación, sus duraciones y la información sobre los puntos artísticos, calcule la máxima puntuación artística total que puede obtener Bitaro.

Entrada

Lee los siguientes datos de la entrada estándar. Todos los valores de la entrada son números enteros.

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

Salida

Escribe una línea en la salida estándar. Debe contener la máxima puntuación artística total que puede obtener Bitaro.

Restricciones

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

Subtareas

1. (5 puntos) $N \le 200\,000$, $M \le 200\,000$, $S_1 = \cdots = S_N = T_1 = \cdots = T_M$.
2. (3 puntos) $N \le 12$, $M \le 12$, $P_i = 1$ ($1 \le i \le N$), $Q_j = 1$ ($1 \le j \le M$).
3. (7 puntos) $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 puntos) $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 puntos) $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 puntos) $1 \le P_i$ ($1 \le i \le N$), $1 \le Q_j$ ($1 \le j \le M$).
7. (17 puntos) $N \le 200\,000$, $M \le 200\,000$.
8. (9 puntos) Sin restricciones adicionales.

Ejemplos

Entrada 1

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

Salida 1

6

Nota

Esta entrada de ejemplo satisface las restricciones de la subtarea 2.

En esta entrada de ejemplo, Bitaro puede realizar los pasos de preparación, por ejemplo, de la siguiente manera:

1. Realiza el primer paso de JOI Curry. Lo termina $3$ minutos después del inicio del concurso. Como está dentro de los primeros $6$ minutos, obtiene $1$ punto.
2. Realiza el primer paso de IOI Donburi. Lo termina $5$ minutos después del inicio del concurso. Como no está dentro del primer minuto, no obtiene puntos artísticos.
3. Realiza el segundo paso de IOI Donburi. Lo termina $8$ minutos después del inicio del concurso. Como está dentro de los primeros $8$ minutos, obtiene $1$ punto.
4. Realiza el segundo paso de JOI Curry. Lo termina $10$ minutos después del inicio del concurso. Como está dentro de los primeros $11$ minutos, obtiene $1$ punto.
5. Realiza el tercer paso de IOI Donburi. Lo termina $12$ minutos después del inicio del concurso. Como está dentro de los primeros $13$ minutos, obtiene $1$ punto.
6. Realiza el cuarto paso de IOI Donburi. Lo termina $13$ minutos después del inicio del concurso. Como está dentro de los primeros $13$ minutos, obtiene $1$ punto.
7. Realiza el tercer paso de JOI Curry. Lo termina $15$ minutos después del inicio del concurso. Como está dentro de los primeros $15$ minutos, obtiene $1$ punto.

La puntuación artística total es de $6$ puntos. No puede obtener más de $6$ puntos, así que se debe imprimir 6.

Entrada 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

Salida 2

63

Nota

Esta entrada de ejemplo satisface las restricciones de la subtarea 1.

Entrada 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

Salida 3

99