$$$n$$$ 男孩和 $$$m$$$ 女孩来参加聚会。每个男孩都给每个女孩一些整数数量的糖果(可能是零)。所有男孩都用从 $$$1$$$ 到 $$$n$$$ 的整数编号,所有女孩都用从 $$$1$$$ 到 $$$m$$$ 的整数编号。对于所有 $$$1 \leq i \leq n$$$,第 $$$i$$$ 个男孩向某个女孩赠送的糖果的最小数量等于 $$$b_i$$$;对于所有 $$$1 \leq j \leq m$$$,第 $$$j$$$ 个女孩从某个男孩收到的糖果的最大数量等于 $$$g_j$$$。
更正式地说,令 $$$a_{i,j}$$$ 为第 $$$i$$$ 个男孩送给第 $$$j$$$ 个女孩的糖果数量。那么 $$$b_i$$$ 恰好等于 $$$a_{i,1}, a_{i,2}, \ldots, a_{i,m}$$$ 中的最小值,并且 $$$g_j$$$ 恰好等于 $$$b_{1,j}, b_{2,j}, \ldots, b_{n,j}$$$ 中的最大值。
您对男孩可以呈现的糖果的最小总数感兴趣,因此您需要最小化所有 $$$(i,j)$$$ 的 $$$a_{i,j}$$$ 总和,使得 $$$1 \leq i \leq n$$$ 和 $$$1 \leq j \leq m$$$。给你数字 $$$b_1, \ldots, b_n$$$ 和 $$$g_1, \ldots, g_m$$$,确定这个数字。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$,用空格分隔——分别是男孩和女孩的数量($$$2 \leq n, m \leq 100\,000$$$)。第二行包含 $$$n$$$ 整数 $$$b_1, \ldots, b_n$$$,以空格分隔 — $$$b_i$$$ 等于第 $$$i$$$ 个男孩送给某个女孩的糖果的最小数量 ($$$0 \leq b_i \leq 10^8$$$)。第三行包含 $$$m$$$ 整数 $$$g_1, \ldots, g_m$$$,以空格分隔 — $$$g_j$$$ 等于第 $$$j$$$ 个女孩从某个男孩那里收到的糖果的最大数量 ($$$0 \leq g_j \leq 10^8$$$)。
输出
如果所描述的情况不可能,则打印$$$-1$$$。在另一种情况下,打印男孩可以呈现并且所有条件都可以满足的糖果的最小总数。
示例
输入 #1
3 2 1 2 1 3 4
输出 #1
12
输入 #2
2 2 0 1 1 0
输出 #2
-1
输入 #3
2 3 1 0 1 1 2
输出 #3
4
注意
在第一个测试中,男孩可以赠送的糖果的最小总数等于 $$$12$$$。这是可能的,例如,如果第一个男孩向第一个女孩和第二个女孩分别展示了 $$$1$$$ 和 $$$4$$$ 糖果,第二个男孩展示了 $$$3$$$ 和 $$$2$$$ 糖果,第三个男孩分别展示了 $$$1$$$ 和 $$$1$$$ 糖果。很容易看出,所有条件都满足,糖果总数等于 $$$12$$$。
在第二次测试中,男孩们不可能以所有陈述都满足的方式呈现糖果。
在第三个测试中,男孩们可以展示的糖果的最小总数等于$$$4$$$。例如,如果第一个男孩分别向第一个、第二个、第三个女孩赠送$$$1$$$、$$$1$$$、$$$2$$$糖果,并且第二个男孩没有为每个女孩赠送糖果,则这是可能的。很容易看出,所有条件都满足,糖果总数等于 $$$4$$$。