Serious Business

문제

Dima is taking part in a show organized by his friend Peter, the show is called <<Peter helps his fellow bro to get a job>>. In this show Dima is required to cross a $3\times n3\; \backslash times\; n$ rectangular field, consisting of $33$ rows and $nn$ columns. Each row has its cells indexed from $11$ to $nn$, from left to right.

Each cell of the filed contains an integer $a_{i,j}a\_\{i,j\}$. Initially Dima's score equals zero, and whenever Dima reaches a cell in row $ii$ and column $jj$, his score changes by $a_{i,j}a\_\{i,j\}$. Note that, the score might become negative.

Initially all cells in the first and in 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 $qq$ special offers in the show, $ii$-th special offer allows Dima to mark cells in the second row between $l_{i}l\_i$ and $r_{i}r\_i$, though Dima's score changes by $k_{i}k\_i$ whenever he accepts the special offer. Dima is allowed to use as many special offers as he pleases, and might mark the same cell as available multiple times.

Dima starts his journey in the first row and in the first column and would like to reach the cell in the third row and in the last column. 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+1n+1$ moves in total, out of which $n-1n-1$ would be horizontal and $22$ --- 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.

입력

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

The next three lines describe the field, $ii$-th of them contains $nn$ integers $a_{i1}a\_\{i1\}$, $a_{i2}a\_\{i2\}$, $\dots \backslash ldots$, $a_{in}a\_\{in\}$ ($-{10}^9\le a_{ij}\le {10}^9)-10^9\; \backslash le\; a\_\{ij\}\; \backslash le\; 10^9)$ --- the values in the $ii$-th row.

The next $qq$ lines describe special offers: $ii$-th offer is described by 3 integers $l_{i}l\_i$, $r_{i}r\_i$ and $k_{i}k\_i$ ($1\le l_i\le r_i\le n1\; \backslash leq\; l\_i\; \backslash leq\; r\_i\; \backslash leq\; n$, $1\le k_i\le {10}^{9}1\backslash leq\; k\_i\backslash leq\; 10^9$) --- the segment that is being unblocked and the cost of this special offer.

출력

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

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