You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

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$。