Minimum Spanning Tree on a Grid Graph

Given a grid graph of size $n \times m$ with rows numbered from $1$ to $n$ and columns numbered from $1$ to $m$. Each vertex is denoted by its coordinates $(r, c)$. There is an edge between $(i, j)$ and $(i, j+1)$ with weight $a_i$ for $1 \le i \le n$ and $1 \le j < m$, and an edge between $(i, j)$ and $(i+1, j)$ with weight $b_j$ for $1 \le i < n$ and $1 \le j \le m$. Your task is to compute the total weight of the minimum spanning tree (MST) for this graph.

inputFormat

The input consists of three lines. The first line contains two integers $n$ and $m$. The second line contains $n$ integers $a_1, a_2, \ldots, a_n$. The third line contains $m$ integers $b_1, b_2, \ldots, b_m$.

outputFormat

Output a single integer representing the total weight of the minimum spanning tree.

sample

2 3
1 3
2 1 4

8