Description

Given an $n\times m$ grid graph, rows are numbered from $1\sim n$ and columns are numbered from $1\sim m$. Each point can be represented by its row number $r$ and column number $c$ as $(r, c)$.

There is an edge with weight $a_i$ between points $(i,j)$ and $(i,j+1)$, where $1\le i\le n, 1\le j<m$.

There is an edge with weight $b_j$ between points $(i, j)$ and $(i+1,j)$, where $1\le i< n, 1\le j \le m$.

Please find the minimum spanning tree of this grid graph.

Input Format

The first line contains two positive integers $n, m$, representing the number of rows and columns.

The second line contains $n$ positive integers, representing $a_i$.

The third line contains $m$ positive integers, representing $b_j$.

Output Format

Output a single integer in one line, representing the answer.

3 3
2 4 3
1 3 2

16

Hint

Explanation of Sample Input/Output 1

The edges in the minimum spanning tree include: all edges in the first row, and all edges in the first, second, and third columns.

Constraints

For $20\%$ of the testdata, $n, m\le 3$, $a_i, b_j \le 10$.

For $40\%$ of the testdata, $n, m\le 20$, $a_i, b_j\le 100$.

For $64\%$ of the testdata, $n, m\le 300$, $a_i, b_j\le 1000$.

For $100\%$ of the testdata, $3\le n, m \le 3\times 10^5$, $1 \le a_i, b_j\le 10^5$.

Translated by ChatGPT 5