CF1648D.Serious Business

Dima is taking part in a show organized by his friend Peter. In this show Dima is required to cross a $3 \times n$ rectangular field. Rows are numbered from $1$ to $3$ and columns are numbered from $1$ to $n$.

The cell in the intersection of the $i$-th row and the $j$-th column of the field contains an integer $a_{i,j}$. Initially Dima's score equals zero, and whenever Dima reaches a cell in the row $i$ and the column $j$, his score changes by $a_{i,j}$. Note that the score can become negative.

Initially all cells in the first and the third row are marked as available, and all cells in the second row are marked as unavailable. However, Peter offered Dima some help: there are $q$ special offers in the show, the $i$-th special offer allows Dima to mark cells in the second row between $l_i$ and $r_i$ as available, though Dima's score reduces by $k_i$ whenever he accepts a special offer. Dima is allowed to use as many special offers as he wants, and might mark the same cell as available multiple times.

Dima starts his journey in the cell $(1, 1)$ and would like to reach the cell $(3, n)$. He can move either down to the next row or right to the next column (meaning he could increase the current row or column by 1), thus making $n + 1$ moves in total, out of which exactly $n - 1$ would be horizontal and $2$ would be vertical.

Peter promised Dima to pay him based on his final score, so the sum of all numbers of all visited cells minus the cost of all special offers used. Please help Dima to maximize his final score.

迪马正在参加他的朋友彼得组织的一场表演。在该表演中，迪马需要穿越一个 $3 \times n$ 的矩形场地。行编号为 $1$ 至 $3$，列编号为 $1$ 至 $n$。

位于第 $i$ 行、第 $j$ 列的格子中包含一个整数 $a_{i,j}$。迪马初始得分为 $0$；每当他到达第 $i$ 行、第 $j$ 列的格子时，其得分将增加 $a_{i,j}$（注意：得分可能变为负数）。

初始时，第一行和第三行的所有格子均标记为“可用”，而第二行的所有格子均标记为“不可用”。然而，彼得向迪马提供了一些帮助：表演中共有 $q$ 个特殊优惠，其中第 $i$ 个特殊优惠允许迪马将第二行中列号在区间 $[l_i, r_i]$ 内的所有格子标记为“可用”，但迪马每接受一个特殊优惠，其最终得分将减少 $k_i$。迪马可以任意多次使用特殊优惠，且同一格子可能被多次标记为“可用”。

迪马从格子 $(1, 1)$ 出发，目标是到达格子 $(3, n)$。他每次只能向下移动到下一行，或向右移动到下一列（即当前行号或列号恰好加 $1$），因此总共需进行 $n + 1$ 次移动，其中恰好 $n - 1$ 次为水平移动（向右），$2$ 次为垂直移动（向下）。

彼得承诺将根据迪马的最终得分向其支付报酬，该最终得分等于所有经过格子中数值之和，减去所使用特殊优惠的总代价。请帮助迪马最大化其最终得分。

The first input line contains two integers $n$ and $q$ ($1 \le n, q \le 500\,000$) — the number of columns in the field and the number of special offers.

The next three lines describe the field, $i$-th of them contains $n$ integers $a_{i1}$, $a_{i2}$, ..., $a_{in}$ ($-10^9 \le a_{ij} \le 10^9)$ — the values in the $i$-th row.

The next $q$ lines describe special offers: the $i$-th offer is described by 3 integers $l_i$, $r_i$ and $k_i$ ($1 \leq l_i \leq r_i \leq n$, $1\leq k_i\leq 10^9$) — the segment that becomes unblocked and the cost of this special offer.

第一行输入包含两个整数 $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$）描述—— 分别表示变为畅通的区间以及该特殊优惠的费用。

Output one integer — the maximum final score Dima can achieve.

输出一个整数——Dima 能达到的最高最终得分。

In the first example, it is optimal to use Peter's second offer of $4$ rubles and go through the cells $(1, 1)$, $(1, 2)$, $(1, 3)$, $(2, 3)$, $(3, 3)$, $(3, 4)$, earning $1 + 0 + 2 + 9 + 4 + 1 - 4 = 13$ rubles in total.

In the second example, it is optimal to use Peter's second and third offers of $2$ and $3$ rubles, respectively, and go through the cells $(1, 1)$, $(2, 1)$, $(2, 2)$, $(2, 3)$, $(2, 4)$, $(3, 4)$, $(3, 5)$, earning $-20 + 1 + 3 + 3 + 6 + 6 + 2 - 2 - 3= -4$ rubles.

在第一个例子中，最优策略是使用彼得的第二个报价（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$ 卢布。