시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초 512 MB444100.000%

문제

Consider a grid graph: the vertices are lined up into a grid of $H$ rows by $W$ columns. Let us denote the vertex in the $i$-th row and $j$-th column as $(i, j)$.

To define the weights of the graph edges, we will consider four non-decreasing sequences, $A$, $B$, $C$, and $D$, consisting of $H-1$, $W$, $H$, and $W-1$ positive integers, respectively:

  • there is a bidirectional edge connecting vertices $(i, j)$ and $(i+1, j)$ of weight $A_i + B_j$ for all $i$ and $j$ such that $1 \le i \le H-1$ and $1 \le j \le W$;
  • there is a bidirectional edge connecting vertices $(i, j)$ and $(i, j+1)$ of weight $C_i + D_j$ for all $i$ and $j$ such that $1 \le i \le H$ and $1 \le j \le W-1$;
  • the graph contains no other edges.

Find the total weight of the edges in the minimal spanning tree of this graph.

입력

The first line of input contains two positive integers $H$ and $W$ ($2 \le H, W \le 10^5$).

The second line contains $H-1$ integers $A_i$: the elements of the sequence $A$.

The third line contains $W$ integers $B_i$: the elements of the sequence $B$.

The fourth line contains $H$ integers $C_i$: the elements of the sequence $C$.

The fifth line contains $W-1$ integers $D_i$: the elements of the sequence $D$.

It is guaranteed that $A_{i-1} \le A_{i}$, $B_{i-1} \le B_{i}$, $C_{i-1} \le C_{i}$, and $D_{i-1} \le D_{i}$ for $i>1$, and additionally, $1 \le A_i, B_i, C_i, D_i \le 10^6$.

출력

Print the total weight of the edges in the minimal spanning tree of the given graph. Note that the answer may not fit into a 32-bit integer.

예제 입력 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