CF457B Distributed Join

Piegirl 被要求为分布式数据库系统实现两张表的连接操作，并尽量减少网络流量。 假设她需要连接两张表，$A$ 和 $B$。它们各自有若干行，并分布在数量不同的分区上。表 $A$ 分布在第一个集群中的 $m$ 个分区中，第 $i$ 个分区包含 $A$ 表的 $a_i$ 行。同样，包含 $B$ 表的第二个集群有 $n$ 个分区，第 $i$ 个分区包含 $B$ 表的 $b_i$ 行。 每次网络操作可以将任意一个分区中的一行复制到任意其他分区。在最终结果中，对于 $A$ 表的每一行与 $B$ 表的每一行，都需要存在某个分区包含这两行。请你计算完成上述目标所需的最小复制操作次数。

第一行包含两个整数 $m$ 和 $n$（$1 \leq m, n \leq 10^{5}$）。 第二行包含 $m$ 个用空格分隔的整数 $a_{i}$（$1 \leq a_{i} \leq 10^{9}$），描述第一个集群中各分区 $A$ 表行数。 第三行包含 $n$ 个用空格分隔的整数 $b_{i}$（$1 \leq b_{i} \leq 10^{9}$），描述第二个集群中各分区 $B$ 表行数。

输出一个整数，表示实现目标所需的最小复制操作次数。

在第一个样例中，可以将所有行移动到第二个集群的第二个分区，这共需 $2+6+3=11$ 次操作。 在第二个样例中，Piegirl 可以把 $B$ 表的每一行分别复制到第一个集群的每个分区，需要 $2 \times 3 = 6$ 次操作。 由 ChatGPT 5 翻译