Повар Bitaro участвует в кулинарном соревновании. Участнику этого соревнования нужно приготовить два блюда: IOI Donburi и JOI Curry.

Приготовление IOI Donburi состоит из $N$ этапов. Этап с номером $i$ ($1 \le i \le N$) занимает ровно $A_i$ минут. Изначально можно выполнить только первый этап. Чтобы выполнить этап с номером $i$ ($2 \le i \le N$), нужно закончить этап с номером $i-1$.

Приготовление JOI Curry состоит из $M$ этапов. Этап с номером $j$ ($1 \le j \le M$) занимает ровно $B_j$ минут. Изначально можно выполнить только первый этап. Чтобы выполнить этап с номером $j$ ($2 \le j \le M$), нужно закончить этап с номером $j-1$.

Этапы требуют сосредоточенности, поэтому, начав один этап, нельзя выполнять другие этапы до его завершения. Между этапами можно переключаться с одного блюда на другое. После начала соревнования нельзя отдыхать, пока оба блюда не будут готовы.

Кроме того, на этом соревновании участнику начисляются баллы за артистизм следующим образом.

• Если он завершает этап с номером $i$ ($1 \le i \le N$) приготовления IOI Donburi не позднее чем через $S_i$ минут после начала соревнования, он получает $P_i$ баллов. Значение $P_i$ может быть отрицательным.
• Если он завершает этап с номером $j$ ($1 \le j \le M$) приготовления JOI Curry не позднее чем через $T_j$ минут после начала соревнования, он получает $Q_j$ баллов. Значение $Q_j$ может быть отрицательным.

Bitaro хочет максимизировать общую сумму баллов за артистизм.

Напишите программу, которая по числу этапов приготовления, времени их выполнения и информации о баллах за артистизм вычисляет максимальную общую сумму баллов за артистизм, которую может получить Bitaro.

Входные данные

Прочитайте следующие данные из стандартного ввода. Все входные значения — целые числа.

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

Выходные данные

Выведите в стандартный вывод одну строку, содержащую максимальную общую сумму баллов за артистизм, которую может получить Bitaro.

Ограничения

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

Подзадачи

1. (5 баллов) $N \le 200\,000$, $M \le 200\,000$, $S_1 = \cdots = S_N = T_1 = \cdots = T_M$.
2. (3 балла) $N \le 12$, $M \le 12$, $P_i = 1$ ($1 \le i \le N$), $Q_j = 1$ ($1 \le j \le M$).
3. (7 баллов) $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 баллов) $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 баллов) $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 баллов) $1 \le P_i$ ($1 \le i \le N$), $1 \le Q_j$ ($1 \le j \le M$).
7. (17 баллов) $N \le 200\,000$, $M \le 200\,000$.
8. (9 баллов) Дополнительных ограничений нет.

Примеры

Входные данные 1

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

Выходные данные 1

6

Примечание

Этот пример удовлетворяет ограничениям подзадачи 2.

В этом примере Bitaro может, например, выполнять этапы приготовления следующим образом:

1. Он выполняет первый этап приготовления JOI Curry и заканчивает его через 3 минуты после начала соревнования. Поскольку прошло не более 6 минут, он получает 1 балл.
2. Он выполняет первый этап приготовления IOI Donburi и заканчивает его через 5 минут после начала соревнования. Поскольку прошло более 1 минуты, он не получает баллов за артистизм.
3. Он выполняет второй этап приготовления IOI Donburi и заканчивает его через 8 минут после начала соревнования. Поскольку прошло не более 8 минут, он получает 1 балл.
4. Он выполняет второй этап приготовления JOI Curry и заканчивает его через 10 минут после начала соревнования. Поскольку прошло не более 11 минут, он получает 1 балл.
5. Он выполняет третий этап приготовления IOI Donburi и заканчивает его через 12 минут после начала соревнования. Поскольку прошло не более 13 минут, он получает 1 балл.
6. Он выполняет четвёртый этап приготовления IOI Donburi и заканчивает его через 13 минут после начала соревнования. Поскольку прошло не более 13 минут, он получает 1 балл.
7. Он выполняет третий этап приготовления JOI Curry и заканчивает его через 15 минут после начала соревнования. Поскольку прошло не более 15 минут, он получает 1 балл.

Общая сумма баллов за артистизм равна 6. Получить более 6 баллов невозможно, поэтому выведите 6.

Входные данные 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

Выходные данные 2

63

Примечание

Этот пример удовлетворяет ограничениям подзадачи 1.

Входные данные 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

Выходные данные 3

99