D. Бизнес-шоу
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дима находится на шоу от бизнесмена Петра. В этом шоу Диме предстоит пройтись по дорожке, которая является прямоугольником $$$3 \times n$$$, где строки пронумерованы от $$$1$$$ до $$$3$$$ сверху вниз, а столбцы от $$$1$$$ до $$$n$$$ слева направо.

На клетке на пересечении строки $$$i$$$ и столбца $$$j$$$ написано число $$$a_{i,j}$$$. Изначально у Димы есть баланс, равный нулю, и когда Дима наступает на клетку в $$$i$$$-й строке и $$$j$$$-м столбце, его баланс меняется на $$$a_{i,j}$$$ рублей. Баланс может становиться отрицательным.

Дима может заходить на любые клетки первой и третьей строки, но изначально клетки второй строки для него недоступны. Однако есть $$$q$$$ предложений от бизнесмена Петра, которые могут сделать их доступными: $$$i$$$-е предложение позволяет разблокировать все клетки второй строки на отрезке с $$$l_i$$$ по $$$r_i$$$, заплатив за это $$$k_i$$$ рублей. Дима может воспользоваться любым количеством таких предложений, а также разблокировать одну и ту же клетку несколько раз.

Дима изначально стоит на клетке в клетке $$$(1, 1)$$$ и хочет попасть в клетку $$$(3, n)$$$. За один ход Дима может подвинуться на 1 вправо или вниз, то есть увеличить на 1 номер строки или столбца. Таким образом, всего в процессе пути Дима сделает $$$n + 1$$$ ход, из которых ровно $$$n - 1$$$ будет по горизонтали и $$$2$$$ по вертикали.

Выигрыш Димы будет равен финальному балансу после совершения всех ходов, то есть сумме чисел на всех посещённых клетках за вычетом стоимости всех использованных предложений. Ваша задача — определить максимальный возможный выигрыш Димы.

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

В первой строке даны два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n, q \le 500\,000$$$) — длина прямоугольника и число возможных отрезков для разблокировки.

В следующих трёх строках описываются числа в прямоугольнике, в $$$i$$$-й строке даны $$$n$$$ целых чисел $$$a_{i1}$$$, $$$a_{i2}$$$, ..., $$$a_{in}$$$ ($$$-10^9 \le a_{ij} \le 10^9)$$$ — числа в $$$i$$$-й строке прямоугольника.

В следующих $$$q$$$ строках описываются доступные предложения для разблокировки отрезков, в $$$i$$$-й из них даны три целых числа $$$l_i$$$, $$$r_i$$$ и $$$k_i$$$ ($$$1 \leq l_i \leq r_i \leq n$$$, $$$1\leq k_i\leq 10^9$$$) — границы разблокируемого отрезка и стоимость предложения.

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

Выведите одно число — максимальный возможный выигрыш Димы.

Примеры
Входные данные
4 3
1 0 2 -1
-3 1 9 2
3 2 4 1
1 2 5
2 3 4
1 4 14
Выходные данные
13
Входные данные
5 4
-20 -10 -11 -10 1
1 3 3 6 3
14 -20 3 6 2
1 5 13
1 2 2
3 5 3
2 3 1
Выходные данные
-4
Примечание

В первом примере оптимально воспользоваться вторым предложением Петра за $$$4$$$ рубля и пройти по клеткам $$$(1, 1)$$$, $$$(1, 2)$$$, $$$(1, 3)$$$, $$$(2, 3)$$$, $$$(3, 3)$$$, $$$(3, 4)$$$, заработав $$$1 + 0 + 2 + 9 + 4 + 1 - 4 = 13$$$ рублей.

Во втором примере оптимально воспользоваться вторым и третьим предложением Петра за $$$2$$$ и $$$3$$$ рубля соответственно, и пройти по клеткам $$$(1, 1)$$$, $$$(2, 1)$$$, $$$(2, 2)$$$, $$$(2, 3)$$$, $$$(2, 4)$$$, $$$(3, 4)$$$, $$$(3, 5)$$$, заработав $$$-20 + 1 + 3 + 3 + 6 + 6 + 2 - 2 - 3= -4$$$ рубля.