AT_codefestival_2016_qualB_c Gr-idian MST

在 $xy$ 平面上，满足 $0 \leq x \leq W,\ 0 \leq y \leq H$ 的区域内，每一个 $x, y$ 都为整数的点上都有一座房子。 对于所有 $x$ 坐标相同且 $y$ 坐标之差为 $1$，或者 $y$ 坐标相同且 $x$ 坐标之差为 $1$ 的两个点，如果这两个点上都有房子，则这两个点之间有一条未铺设的道路。 将坐标为 $(i, j)$ 和 $(i+1, j)$ 的房子之间的道路铺设需要花费 $p_i$（与 $j$ 的值无关），将坐标为 $(i, j)$ 和 $(i, j+1)$ 的房子之间的道路铺设需要花费 $q_j$（与 $i$ 的值无关）。 高桥君希望选择性地铺设一些道路，使得仅通过已铺设的道路，任意两座房子之间都可以互相到达。请你求出所需的最小总花费。

输入以如下格式从标准输入读入。 > $W$ $H$ > $p_0\ p_1\ \cdots\ p_{W-1}$ > $q_0\ q_1\ \cdots\ q_{H-1}$

输出一个整数，表示最小总花费。

## 限制条件 - $1 \leq W, H \leq 10^5$ - $1 \leq p_i \leq 10^8\ (0 \leq i \leq W-1)$ - $1 \leq q_j \leq 10^8\ (0 \leq j \leq H-1)$ - $p_i\ (0 \leq i \leq W-1)$ 均为整数 - $q_j\ (0 \leq j \leq H-1)$ 均为整数 ## 样例解释 1 只需铺设以下 $8$ 条道路即可： - 连接 $(0,0)$ 和 $(0,1)$ 的道路 - 连接 $(0,1)$ 和 $(1,1)$ 的道路 - 连接 $(0,2)$ 和 $(1,2)$ 的道路 - 连接 $(1,0)$ 和 $(1,1)$ 的道路 - 连接 $(1,0)$ 和 $(2,0)$ 的道路 - 连接 $(1,1)$ 和 $(1,2)$ 的道路 - 连接 $(1,2)$ 和 $(2,2)$ 的道路 - 连接 $(2,0)$ 和 $(2,1)$ 的道路 由 ChatGPT 4.1 翻译