P5687 [CSP-S 2019 Jiangxi] Grid Graph

JXCSP-S T3

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

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 a single integer in one line, representing the answer.

#### 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