Problem Description

There is a grid graph with vertices arranged in $ H $ rows and $ W $ columns.

The vertex in the $ i $ -th row and $ j $ -th column ( $1 \le i \le H, 1 \le j \le W$ ) is denoted as $ (i, j) $.

There are non-decreasing positive integer sequences $ A, B, C, D $ with lengths $ H-1, W, H, W-1 $ respectively.

The vertex $ (i, j) $ and the vertex $ (i+1, j) $ are connected by an undirected edge with weight $ A_i + B_j $. ( $1 \le i \le H-1, 1 \le j \le W$ )

The vertex $ (i, j) $ and the vertex $ (i, j+1) $ are connected by an undirected edge with weight $ C_i + D_j $. ( $1 \le i \le H, 1 \le j \le W-1$ )

No other edges exist.

Find the sum of the weights of the edges included in the minimum spanning tree of this graph.

Input Format

The input is given from the standard input in the following format:

$ H $ $ W $ $ A_1 $ $ A_2 $ $\ldots$ $ A_{H-1} $ $ B_1 $ $ B_2 $ $\ldots$ $ B_{W-1} $ $ B_W $ $ C_1 $ $ C_2 $ $\ldots$ $ C_{H-1} $ $ C_H $ $ D_1 $ $ D_2 $ $\ldots$ $ D_{W-1} $

Output Format

Output the sum of the weights of the edges included in the minimum spanning tree of the grid graph.

Note that the answer may not fit into a 32-bit integer.

Sample Input and Output

Sample Input #1

2 3
1
1 3 6
1 4
1 2

Sample Output #1

17

Sample Input #2

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

Sample Output #2

173

Notes/Hints

Constraints

• $2 \le H \le 10^5$
• $2 \le W \le 10^5$
• $1 \le A_i \le 10^6 \ (1 \le i \le H-1)$
• $1 \le B_j \le 10^6 \ (1 \le j \le W)$
• $1 \le C_i \le 10^6 \ (1 \le i \le H)$
• $1 \le D_j \le 10^6 \ (1 \le j \le W-1)$
• $A_i \le A_{i+1} \ (1 \le i \le H-2)$
• $B_j \le B_{j+1} \ (1 \le j \le W-1)$
• $C_i \le C_{i+1} \ (1 \le i \le H-1)$
• $D_j \le D_{j+1} \ (1 \le j \le W-2)$

Sample Explanation 1

The given graph looks like the figure above. The sum of the weights of the edges included in the minimum spanning tree of this graph is $ 17 $.

见题面 Input 部分

见题面 Output 部分