Piegirl 被要求为分布式数据库系统实现两个表连接操作,最大限度地减少网络流量。
假设她想要连接两个表 A 和 B。每个表都有一定数量的行,这些行分布在不同数量的分区上。表A分布在由m个分区组成的第一个集群上。索引为 i 的分区具有来自 A 的 ai 行。类似地,包含表 B 的第二个簇具有 n 个分区,第 i 个分区具有来自 B 的 bi 行。
在一次网络操作中,她可以将一行从任何分区复制到任何其他分区。最后,对于 A 中的每一行和 B 中的每一行,应该有一个包含这两行的分区。确定实现此目的所需的最少网络操作数。
输入
第一行包含两个整数,m 和 n (1 ≤ m, n ≤ 105)。第二行包含第一个簇的描述,其中 m 个空格分隔的整数 ai (1 ≤ ai ≤ 109)。类似地,第三行描述了具有 n 个空格分隔的整数 bi (1 ≤ bi ≤ 109) 的第二个簇。
输出
打印一个整数 — 复制操作的最少次数。
示例
输入 #1
2 2 2 6 3 100
输出 #1
11
输入 #2
2 3 10 10 1 1 1
输出 #2
6
注意
在第一个示例中,将所有行移动到第二个集群的第二个分区是有意义的,这是通过 2 + 6 + 3 = 11 次操作实现的
在第二个示例中,Piegirl 可以将 B 中的每一行复制到第一个集群的两个分区,这需要 2·3 = 6 次复制操作。