题目描述

迪玛正在参加由商人彼得主持的一档名为《彼得帮助普通小伙找兼职》的节目。在这档节目中，迪玛需要穿越一个由 $3$ 行 $n$ 列组成的矩形路径。每一行中的单元格从左到右编号为 $1$ 到 $n$。

每个单元格上写着一个数字 $a_{i,j}$。迪玛初始余额为 $0$，当他踏上第 $i$ 行第 $j$ 列的单元格时，他的余额会增加 $a_{i,j}$ 卢布。余额可能变为负值。

迪玛可以任意进入第一行和第三行的单元格，但第二行的单元格最初对他来说是不可进入的。然而，商人彼得提供了 $q$ 个提议，可以解锁第二行的部分单元格：第 $i$ 个提议可以解锁第二行从 $l_i$ 到 $r_i$ 的所有单元格，但需要支付 $k_i$ 卢布（即余额减少 $k_i$）。迪玛可以选择任意数量的提议，甚至多次解锁同一个单元格。

迪玛初始位置在第一行第一列的单元格，目标是到达第三行第 $n$ 列的单元格。每次移动，迪玛可以向右或向下移动 $1$ 格，即增加行号或列号 $1$。因此，在整个路径中，迪玛总共会进行 $n+1$ 次移动，其中 $n-1$ 次是水平移动，$2$ 次是垂直移动。

迪玛的最终收益等于完成所有移动后的最终余额，即访问的所有单元格上数字之和减去所有使用的提议的费用。你的任务是确定迪玛可能获得的最大收益。

输入格式

第一行包含两个整数 $n$ 和 $q$ $(1 \leq n, q \leq 500000)$，分别表示矩形的列数和可用的解锁提议数量。

接下来的三行描述矩形中的数字，第 $i$ 行包含 $n$ 个整数 $a_{i1}, a_{i2}, \ldots, a_{in}$ $(-10^{9} \leq a_{ij} \leq 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})$，分别表示第 $i$ 个提议的解锁范围和解锁所有单元格的费用。

输出格式

输出一个整数，即迪玛可能获得的最大收益。

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

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。