Dima 正在参加他的朋友 Peter 组织的一场表演。在这个节目中,迪马需要穿过 $$$3 \times n$$$ 矩形场地。行的编号从 $$$1$$$ 到 $$$3$$$,列的编号从 $$$1$$$ 到 $$$n$$$。
该字段的第 $$$i$$$ 行和第 $$$j$$$ 列相交处的单元格包含一个整数 $$$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, 1)$$$ 中开始他的旅程,并希望到达牢房 $$$(3, n)$$$。他可以向下移动到下一行,也可以向右移动到下一列(这意味着他可以将当前行或列增加 1),从而总共移动 $$$n + 1$$$,其中 $$$n - 1$$$ 是水平的,$$$2$$$ 是垂直的。
彼得答应迪玛根据他的最终分数向他付款,即所有访问过的单元格的所有数字之和减去所有使用的特殊优惠的费用。请帮助迪马最大化他的最终分数。
输入
第一个输入行包含两个整数 $$$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$$$ 个优惠由 3 个整数 $$$l_i$$$、$$$r_i$$$ 和 $$$k_i$$$ 描述 ($$$1 \leq l_i \leq r_i \leq n$$$, $$$1\leq k_i\leq 10^9$$$) — 畅通无阻的路段以及此特别优惠的费用。
输出
输出一个整数——迪玛最终能达到的最高分数。
示例
输入 #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
注意
在第一个示例中,最好使用 Peter 的第二个报价 $$$4$$$ 卢布并遍历单元格 $$$(1, 1)$$$, $$$(1, 2)$$$, $$$(1, 3)$$$, $$$(2, 3)$$$, $$$(3, 3)$$$, $$$(3, 4)$$$,总共赚取$$$1 + 0 + 2 + 9 + 4 + 1 - 4 = 13$$$ 卢布。
在第二个示例中,最佳方案是分别使用 Peter 的第二次和第三次报价 $$$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$$$ 卢布。