O cozinheiro Bitaro está participando de um concurso de culinária. Neste concurso, cada participante deve preparar dois pratos: IOI Donburi e JOI Curry.

O preparo do IOI Donburi consiste em $N$ etapas. A $i$-ésima etapa ($1 \le i \le N$) leva exatamente $A_i$ minutos. Inicialmente, ele só pode executar a primeira etapa. Para executar a $i$-ésima etapa ($2 \le i \le N$), ele precisa ter concluído a $(i-1)$-ésima etapa.

O preparo do JOI Curry consiste em $M$ etapas. A $j$-ésima etapa ($1 \le j \le M$) leva exatamente $B_j$ minutos. Inicialmente, ele só pode executar a primeira etapa. Para executar a $j$-ésima etapa ($2 \le j \le M$), ele precisa ter concluído a $(j-1)$-ésima etapa.

As etapas exigem concentração; portanto, ao começar uma etapa, ele não pode executar outras etapas até terminá-la. Entre as etapas, ele pode trocar de um prato para o outro. Depois que o concurso começa, ele não pode descansar até concluir os dois pratos.

Além disso, neste concurso, cada participante recebe pontos artísticos da seguinte maneira.

• Se ele concluir a $i$-ésima etapa ($1 \le i \le N$) do preparo do IOI Donburi em até $S_i$ minutos após o início do concurso, receberá $P_i$ pontos. O valor de $P_i$ pode ser negativo.
• Se ele concluir a $j$-ésima etapa ($1 \le j \le M$) do preparo do JOI Curry em até $T_j$ minutos após o início do concurso, receberá $Q_j$ pontos. O valor de $Q_j$ pode ser negativo.

Bitaro quer maximizar sua pontuação artística total.

Escreva um programa que, dados os números de etapas de preparo, o tempo que cada uma leva e as informações sobre os pontos artísticos, calcule a maior pontuação artística total que Bitaro pode obter.

Entrada

Leia os seguintes dados da entrada padrão. Todos os valores da entrada são inteiros.

$$ \begin{aligned} &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{aligned} $$

Saída

Escreva uma linha na saída padrão contendo a maior pontuação artística total que Bitaro pode obter.

Restrições

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

Subtarefas

1. (5 pontos) $N \le 200\,000$, $M \le 200\,000$, $S_1 = \cdots = S_N = T_1 = \cdots = T_M$.
2. (3 pontos) $N \le 12$, $M \le 12$, $P_i = 1$ ($1 \le i \le N$), $Q_j = 1$ ($1 \le j \le M$).
3. (7 pontos) $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 pontos) $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 pontos) $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 pontos) $1 \le P_i$ ($1 \le i \le N$), $1 \le Q_j$ ($1 \le j \le M$).
7. (17 pontos) $N \le 200\,000$, $M \le 200\,000$.
8. (9 pontos) Sem restrições adicionais.

Exemplos

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

Saída 1

6

Nota

Esta entrada de exemplo satisfaz as restrições da Subtarefa 2.

Nesta entrada de exemplo, Bitaro pode executar as etapas de preparo, por exemplo, da seguinte maneira:

1. Ele executa a 1ª etapa do JOI Curry e a conclui 3 minutos após o início do concurso. Como isso está dentro do prazo de 6 minutos, ele ganha 1 ponto.
2. Ele executa a 1ª etapa do IOI Donburi e a conclui 5 minutos após o início do concurso. Como isso não está dentro do prazo de 1 minuto, ele não ganha pontos artísticos.
3. Ele executa a 2ª etapa do IOI Donburi e a conclui 8 minutos após o início do concurso. Como isso está dentro do prazo de 8 minutos, ele ganha 1 ponto.
4. Ele executa a 2ª etapa do JOI Curry e a conclui 10 minutos após o início do concurso. Como isso está dentro do prazo de 11 minutos, ele ganha 1 ponto.
5. Ele executa a 3ª etapa do IOI Donburi e a conclui 12 minutos após o início do concurso. Como isso está dentro do prazo de 13 minutos, ele ganha 1 ponto.
6. Ele executa a 4ª etapa do IOI Donburi e a conclui 13 minutos após o início do concurso. Como isso está dentro do prazo de 13 minutos, ele ganha 1 ponto.
7. Ele executa a 3ª etapa do JOI Curry e a conclui 15 minutos após o início do concurso. Como isso está dentro do prazo de 15 minutos, ele ganha 1 ponto.

A pontuação artística total é de 6 pontos. Ele não pode obter mais de 6 pontos, portanto imprima 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

Saída 2

63

Nota

Esta entrada de exemplo satisfaz as restrições da Subtarefa 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

Saída 3

99