Dima 正在参加由他的朋友 Peter 举办的一档节目，节目名为《Peter 帮好兄弟找工作》（Peter helps his fellow bro to get a job）。在节目中，Dima 需要穿越一个 $3 \times n$ 的网格，该网格由 $3$ 行 $n$ 列组成。每行的单元格从左到右依次编号为 $1$ 到 $n$。

网格中的每个单元格都包含一个整数 $a_{i,j}$。最初 Dima 的得分为零，每当 Dima 到达第 $i$ 行第 $j$ 列的单元格时，他的得分就会加上 $a_{i,j}$。注意，得分可能会变成负数。

起初，第一行和第三行的所有单元格都被标记为可用，而第二行的所有单元格都被标记为不可用。然而，Peter 给 Dima 提供了一些帮助：节目中共有 $q$ 个特惠活动。第 $i$ 个特惠活动允许 Dima 将第二行中介于 $l_i$ 和 $r_i$ 之间（包含端点）的单元格标记为可用，但每次接受该特惠时，Dima 的得分会减少 $k_i$。Dima 可以根据需要使用任意数量的特惠，并且可以多次将同一个单元格标记为可用。

Dima 从第一行第一列的单元格出发，目标是到达第三行最后一列的单元格。他每次只能向下移动到下一行，或者向右移动到下一列（即当前行号或列号加 $1$）。因此，他总共会进行 $n + 1$ 次移动，其中 $n - 1$ 次为水平移动，$2$ 次为垂直移动。

Peter 承诺会根据 Dima 的最终得分向他支付报酬，最终得分为所有访问过的单元格中的数值之和，减去所使用的所有特惠活动的总费用。请帮助 Dima 最大化他的最终得分。

输入格式

输入第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 500\,000$），分别表示网格的列数和特惠活动的总数。

接下来的三行描述该网格，其中第 $i$ 行包含 $n$ 个整数 $a_{i,1}, a_{i,2}, \dots, a_{i,n}$（$-10^9 \le a_{i,j} \le 10^9$），表示网格第 $i$ 行中各单元格的数值。

接下来的 $q$ 行描述特惠活动：第 $i$ 个特惠活动由三个整数 $l_i$、$r_i$ 和 $k_i$（$1 \le l_i \le r_i \le n$，$1 \le k_i \le 10^9$）描述，表示被解锁的区间以及该特惠活动的费用。

输出格式

输出一个整数，表示 Dima 所能获得的最高最终得分。

样例

输入样例 1

4 3
1 0 2 -1
-3 1 9 2
3 2 4 1
1 2 5
2 3 4
1 4 14

输出样例 1

13

输入样例 2

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

输出样例 2

-4

子任务

本题的测试集由 6 个测试组（子任务）组成。只有当你的程序通过该子任务中的所有测试点，以及该子任务所依赖的所有子任务中的所有测试点时，你才能获得该子任务的分数。“离线评测（Offline-evaluation）”意味着你不会立即获得该子任务的反馈，只有在比赛结束后才能看到结果。请注意，通过所有样例并不是得分的必要条件。