There is an $n \times m$ grid graph, where the grid point at row $x$ and column $y$ is denoted as $(x, y)$. Given four monotonically non-decreasing arrays $A, B, C, D$, the edge weights of the grid graph are determined by these four arrays as follows:

• The weight of the edge between $(x, y)$ and $(x+1, y)$ is $A_x + B_y$.
• The weight of the edge between $(x, y)$ and $(x, y+1)$ is $C_x + D_y$.

You need to find the size (total weight) of the Minimum Spanning Tree (MST) of this grid graph.

Input

The first line contains two integers $n$ and $m$, representing the size of the grid graph.

The second line contains $n-1$ integers $A_i$, representing array $A$.

The third line contains $m$ integers $B_i$, representing array $B$.

The fourth line contains $n$ integers $C_i$, representing array $C$.

The fifth line contains $m-1$ integers $D_i$, representing array $D$.

Output

Output a single integer representing the size of the Minimum Spanning Tree.

Examples

Input 1

2 3
1
1 3 6
1 4
1 2

Output 1

17

Note 1

The Minimum Spanning Tree contains the following five edges:

• $(1,1) - (2,1): 2$
• $(1,1) - (1,2): 2$
• $(1,2) - (1,3): 3$
• $(1,2) - (2,2): 4$
• $(2,2) - (2,3): 6$

Input 2

See the provided files.

Constraints

For all test cases, it is guaranteed that $2 \leq n, m \leq 10^5$ and $1 \leq A_i, B_i, C_i, D_i \leq 10^6$.

It is guaranteed that $A_i \leq A_{i+1}$, $B_i \leq B_{i+1}$, $C_i \leq C_{i+1}$, and $D_i \leq D_{i+1}$.