CF457B.Distributed Join

Piegirl was asked to implement two table join operation for distributed database system, minimizing the network traffic.

Suppose she wants to join two tables, A and B. Each of them has certain number of rows which are distributed on different number of partitions. Table A is distributed on the first cluster consisting of m partitions. Partition with index i has a__i rows from A. Similarly, second cluster containing table B has n partitions, i-th one having b__i rows from B.

In one network operation she can copy one row from any partition to any other partition. At the end, for each row from A and each row from B there should be a partition that has both rows. Determine the minimal number of network operations to achieve this.

Piegirl 被要求为分布式数据库系统实现两张表的连接（join）操作，并使网络通信量最小化。

假设她需要连接两张表 $A$ 和 $B$。每张表的若干行被分别分布于不同数量的分区中。表 $A$ 分布在由 $m$ 个分区组成的第一个集群中；索引为 $i$ 的分区包含 $a_i$ 行来自 $A$ 的数据。类似地，包含表 $B$ 的第二个集群有 $n$ 个分区，其中第 $i$ 个分区包含 $b_i$ 行来自 $B$ 的数据。

每次网络操作可将任意一个分区中的一行数据复制到任意其他分区。最终，对 $A$ 中的每一行和 $B$ 中的每一行，都必须存在某个分区，该分区同时包含这两行。求达成此目标所需的最少网络操作次数。

First line contains two integer numbers, m and n (1 ≤ m, n ≤ 105). Second line contains description of the first cluster with m space separated integers, a__i (1 ≤ a__i ≤ 109). Similarly, third line describes second cluster with n space separated integers, b__i (1 ≤ b__i ≤ 109).

第一行包含两个整数 $m$ 和 $n$（$1 \le m, n \le 10^5$）。
第二行包含第一个簇的描述，即 $m$ 个用空格分隔的整数 $a_i$（$1 \le a_i \le 10^9$）。
类似地，第三行用 $n$ 个用空格分隔的整数 $b_i$（$1 \le b_i \le 10^9$）描述第二个簇。

Print one integer — minimal number of copy operations.

输出一个整数——最小的复制操作次数。

In the first example it makes sense to move all the rows to the second partition of the second cluster which is achieved in 2 + 6 + 3 = 11 operations

In the second example Piegirl can copy each row from B to the both partitions of the first cluster which needs 2·3 = 6 copy operations.

在第一个例子中，将所有行移动到第二个簇的第二分区是合理的，这需要 $2 + 6 + 3 = 11$ 次操作。

在第二个例子中，Piegirl 可以将 B 中的每一行都复制到第一个簇的两个分区中，这需要 $2·3 = 6$ 次复制操作。