Кухар 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}{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} $$

Вихідні дані

Виведіть один рядок у стандартний вивід. Він має містити найбільшу загальну кількість балів за майстерність, яку може отримати 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. Він виконує 1-й етап JOI Curry. Він завершує його через 3 хвилини після початку конкурсу. Оскільки це не пізніше ніж через 6 хвилин, він отримує 1 бал.
2. Він виконує 1-й етап IOI Donburi. Він завершує його через 5 хвилин після початку конкурсу. Оскільки це пізніше ніж через 1 хвилину, він не отримує балів за майстерність.
3. Він виконує 2-й етап IOI Donburi. Він завершує його через 8 хвилин після початку конкурсу. Оскільки це не пізніше ніж через 8 хвилин, він отримує 1 бал.
4. Він виконує 2-й етап JOI Curry. Він завершує його через 10 хвилин після початку конкурсу. Оскільки це не пізніше ніж через 11 хвилин, він отримує 1 бал.
5. Він виконує 3-й етап IOI Donburi. Він завершує його через 12 хвилин після початку конкурсу. Оскільки це не пізніше ніж через 13 хвилин, він отримує 1 бал.
6. Він виконує 4-й етап IOI Donburi. Він завершує його через 13 хвилин після початку конкурсу. Оскільки це не пізніше ніж через 13 хвилин, він отримує 1 бал.
7. Він виконує 3-й етап 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