Serious Business
Contest: Codeforces Round 775 (Div. 1, based on Moscow Open Olympiad in Informatics)
Difficulty rating: 2800
Tags: data structures, divide and conquer, dp, implementation, shortest paths

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.

Input format:
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.

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

Constraints:
Time limit: 5.0 s
Memory limit: 512.0 MB

Note:
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.

Example input:
4 3
1 0 2 -1
-3 1 9 2
3 2 4 1
1 2 5
2 3 4
1 4 14

Example output:
13

Example input:
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

Example output:
-4

Editorial:
Let's denote $$$pref[i][j] := \sum_{k = 0}^{j - 1} a[i][k]$$$. Then define $$$s$$$ and $$$t$$$ as follows:
$$$$$$ s[i] = pref[0][i + 1] - pref[1][i] $$$$$$
$$$$$$ f[i] = pref[1][i + 1] - pref[2][i] + pref[2][n] $$$$$$
Now we can transform the problem to following: compute $$$\max\limits_{0\leq i\leq j < n} s[i] + f[j] - cost(i, j)$$$ where $$$cost(i, j)$$$ is the minimal cost of unlocking segment $$$[i, j]$$$.
Let's define $$$dp[i]$$$ as the maximum profit for going from $$$(1, 1)$$$ to $$$(2, i)$$$, if the rightmost segment that we have used ends in $$$i$$$ (so it's $$$s[j]$$$ for some $$$j$$$ minus cost of covering segment $$$[i, j]$$$, when we know that there's a segment ending at $$$i$$$).
The calculation of $$$dp$$$ is as follows: for all $$$i$$$ look through each segment, which ends at $$$i$$$, and relax $$$dp[i]$$$ with $$$\max\limits_{l - 1\leq j < i} dp[j] - k$$$. It can be calculated using segment tree.
Now consider the optimal usage of segments. Fix the rightmost segment. The profit for this segment usage should be $$$dp[i] + f[j] + k$$$ for some $$$i, j$$$ on this segment. So we can bruteforce the rightmost segment in our answer and relax the overall answer with $$$\max\limits_{l\leq i\leq j\leq r} dp[i] + f[j] - k$$$. Also there's a case where taking only 1 segment is optimal, then we should relax the answer with $$$\max\limits_{l\leq i\leq j\leq r} s[i] + f[j] - k$$$. We can calculate all of this using segment tree.
Overall complexity is $$$O(q\, log\, n)$$$.