[CSP-S2019 江西] 网格图

JXCSP-S T3

给定一个 $n\times m$ 的网格图，行从 $1\sim n$ 编号，列从 $1\sim m$ 编号，每个点可用它所在的行编号 $r$ 与所在的列编号 $c$ 表示为 $(r, c)$。 点 $(i,j)$ 与 $(i,j+1)$ 间连有一条权值为 $a_i$ 的边，其中 $1\le i\le n, 1\le j<m$。 点 $(i, j)$ 与 $(i+1,j)$ 间连有一条权值为 $b_j$ 的边，其中 $1\le i< n, 1\le j \le m$。 请你求出这个网格图的最小生成树。

第一行两个正整数 $n, m$ 表示行数与列数。 第二行 $n$ 个正整数表示 $a_i$。 第三行 $m$ 个正整数表示 $b_j$。

仅一行一个整数表示答案。

3 3
2 4 3
1 3 2

16

#### 【输入输出样例 1 说明】 最小生成树中的边包括：第一行上的所有边，第一列、第二列、第三列上的所有边。 #### 【数据规模与约定】 对于 $20\%$ 的数据，$n, m\le 3$，$a_i, b_j \le 10$； 对于 $40\%$ 的数据，$n, m\le 20$，$a_i, b_j\le 100$； 对于 $64\%$ 的数据，$n, m\le 300$，$a_i, b_j\le 1000$； 对于 $100\%$ 的数据：$3\le n, m \le 3\times 10^5$，$1 \le a_i, b_j\le 10^5$。