You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目信息

时间限制: 2s

空间限制: 512M

输入文件: challenge.in

输出文件: challenge.out

题目描述

有一个给定的 $n$ 行 $n$ 列的方阵 $A$。方阵 $A$ 中的每个位置有一个非负整数，用 $A_{i,j}$ 表示第 $i$ 行第 $j$ 列的数，$1\le i,j \le n$。

有两个给定的长为 $n$ 的非负整数列，$\{a_i\}$ 和 $\{b_i\}$。

现在你要构造一个同样 $n\times n$ 大小的新的方阵 $B$，满足：

• $B$ 的元素 $B_{i,j} (1\le i,j\le n)$ 都是非负整数。
• $B$ 的每个元素不能超过 $A$ 对应位置的元素。也就是对于任意 $1\le i,j \le n$，必须满足 $0\le B_{i,j}\le A_{i,j}$
• 对于每个 $1\le i\le n$，$B$ 的前 $i$ 行所有元素的和不超过 $a_i$。
• 对于每个 $1\le i\le n$，$B$ 的前 $i$ 列所有元素的和不超过 $b_i$。

问：方阵 $B$ 中的所有元素的和最大可能是多少？

这个问题中，方阵 $A$ 的非零元素个数只有不超过 $m$ 个。具体而言，方阵 $A$ 采用如下方式输入：初始情况下 $A$ 的元素全部为 $0$，然后有 $m$ 次操作，每次给定 $u_i,v_i,c_i$，表示给 $A$ 的第 $u_i$ 行 $v_i$ 列加上 $c_i$。（不保证不同操作中 $u_i,v_i$ 互不相等）

输入格式

为减少输入量，$a,b,u$ 均由差分形式给出。

第一行两个数 $n,m$。

第二行 $n$ 个数，其中第 $i$ 个为 $a_i-a_{i-1}$，设 $a_0=0$。（也就是说输入数组的前缀和才是真正的 $a$）

第三行 $n$ 个数，其中第 $i$ 个为 $b_i-b_{i-1}$，设 $b_0=0$。（也就是说输入数组的前缀和才是真正的 $b$）

接下来 $m$ 行，每行三个数，其中第 $i$ 行为 $u_i-u_{i-1},v_i,c_i$，设 $u_0=0$。（也就是说输入的这些三元组中第一个元素要做前缀和才得到真正的 $u$）。$u_i,v_i,c_i$ 表示给 $A$ 的第 $u_i$ 行 $v_i$ 列加上 $c_i$。

保证这些差分都非负，也就是说 $a,b,u$ 的输入顺序都是单调不降的。

输出格式

一行一个非负整数，表示方阵 $B$ 中的所有元素最大可能的和。

样例

样例输入 1

2 3
2 2
2 2
1 1 2
0 2 2
1 1 2

样例输出 1

4

样例解释 1

还原后的输入为：

$a=b=\{2,4\}$

一个最优解是：

样例输入 2

10 10
1 0 1 1 1 0 1 2 2 1
1 1 0 1 0 1 2 2 1 0
1 8 1
1 4 1
1 3 1
2 6 1
1 6 1
0 1 1
0 4 1
0 9 1
3 2 1
0 10 1

样例输出 2

6

样例解释 2

一个最优解是，$B_{1,8}=B_{5,6}=B_{6,6}=B_{6,9}=B_{9,2}=B_{9,10}=1$，其余位置为 $0$。

数据范围与提示

由于输入量较大，请使用快读。附加文件中附有快读模板。

对于所有数据，$1\le m,n\le 4\times 10^6, 1\le a_i,b_i\le 2\times 10^8, 1\le u_i,v_i\le n, 1\le c_i\le 100$。

对于前 $20\%$ 的数据，$n=m=20,c_i=1$；
对于另外 $20\%$ 的数据，$n=m=10^5,u_i=v_i=i$；
对于另外 $30\%$ 的数据，$n=m=10^5$；
对于另外 $10\%$ 的数据，$n=m=10^6$；
对于另外 $10\%$ 的数据，$n=m=2\times 10^6$；