题目描述

有一张 $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}$。

时间限制：$2\texttt{s}$

空间限制：$512\texttt{MB}$