23108번 - Find the MST for Grid 다국어

문제

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.

제한

힌트