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.