有一张 $n\times m$ 的网格图，第 $x$ 行第 $y$ 列的格点记为 $(x,y)$，给定四个单调不降数组 $A,B,C,D$，网格图的边权由这四个数组决定，具体的：
- $(x,y)$ 和 $(x+1,y)$ 之间的边权为 $A_x+B_y$。
- $(x,y)$ 和 $(x,y+1)$ 之间的边权为 $C_x+D_y$。
你需要求出这张网格图最小生成树的大小。
输入格式
第一行两个整数 $n,m$ 表示网格图大小。
第二行 $n-1$ 个整数 $A_i$ 表示数组 $A$。
第三行 $m$ 个整数 $B_i$ 表示数组 $B$。
第四行 $n$ 个整数 $C_i$ 表示数组 $C$。
第五行 $m-1$ 个整数 $D_i$ 表示数组 $D$。
输出格式
一行一个整数表示最小生成树大小。
样例一
input
2 3 1 1 3 6 1 4 1 2
output
17
explanation
最小生成树包含如下五条边：
- $(1,1) - (2,1): 2$
- $(1,1) - (1,2): 2$
- $(1,2) - (1,3): 3$
- $(1,2) - (2,2): 4$
- $(2,2) - (2,3): 6$
样例二
见下发文件。
数据范围与提示
对于所有数据，保证 $2\leq n,m\leq 10^5, 1\leq A_i,B_i,C_i,D_i\leq 10^6$。
保证 $A_i\leq A_{i+1}, B_i\leq B_{i+1}, C_i\leq C_{i+1}, D_i\leq D_{i+1}$。
| 测试点编号 | $n,m\leq$ | 特殊性质 |
|---|---|---|
| $1\sim 6$ | $10^3$ | 无 |
| $7\sim 12$ | $10^5$ | 存在 $x,y$ 满足 $A_i=x,B_i=y$，即 $A,B$ 数组中所有元素相同 |
| $13\sim 20$ | 无 |
时间限制：$2\texttt{s}$
空间限制：$512\texttt{MB}$