考虑一个网格图：顶点排列成一个 $H$ 行 $W$ 列的网格。我们将第 $i$ 行第 $j$ 列的顶点记为 $(i, j)$。

为了定义图的边权，我们考虑四个非递减序列 $A, B, C$ 和 $D$，它们分别由 $H - 1, W, H$ 和 $W - 1$ 个正整数组成：

• 对于所有满足 $1 \le i \le H - 1$ 和 $1 \le j \le W$ 的 $i$ 和 $j$，存在一条连接顶点 $(i, j)$ 和 $(i + 1, j)$ 的双向边，权重为 $A_i + B_j$；
• 对于所有满足 $1 \le i \le H$ 和 $1 \le j \le W - 1$ 的 $i$ 和 $j$，存在一条连接顶点 $(i, j)$ 和 $(i, j + 1)$ 的双向边，权重为 $C_i + D_j$；
• 图中不存在其他边。

求该图最小生成树的边权总和。

输入格式

第一行包含两个正整数 $H$ 和 $W$ ($2 \le H, W \le 10^5$)。 第二行包含 $H - 1$ 个整数 $A_i$：序列 $A$ 的元素。 第三行包含 $W$ 个整数 $B_i$：序列 $B$ 的元素。 第四行包含 $H$ 个整数 $C_i$：序列 $C$ 的元素。 第五行包含 $W - 1$ 个整数 $D_i$：序列 $D$ 的元素。

保证对于 $i > 1$ 有 $A_{i-1} \le A_i$，$B_{i-1} \le B_i$，$C_{i-1} \le C_i$ 以及 $D_{i-1} \le D_i$，此外 $1 \le A_i, B_i, C_i, D_i \le 10^6$。

输出格式

输出给定图的最小生成树的边权总和。注意答案可能无法用 32 位整数存储。

样例

样例输入 1

2 3
1
1 3 6
1 4
1 2

样例输出 1

17

样例输入 2

4 3
1 13 15
3 6 11
3 6 6 11
9 17

样例输出 2

173