两个玩家 A 和 B 各有一个 $$$n$$$ 整数的列表。他们都希望自己的分数与对手的分数之间的差值最大化。
在一个回合中,玩家可以将列表中的任何元素添加到他的分数中(假设他的列表不为空),之后该元素将从列表中删除。或者从对手的列表中删除一个元素(假设对手的列表不为空)。
请注意,如果列表中存在相同的元素,则上述操作中只有其中一个会受到影响。例如,如果列表中有元素 $$$\{1, 2, 2, 3\}$$$,并且您决定在下一回合中选择 $$$2$$$,则只会删除 $$$2$$$ 的单个实例(并在必要时添加到分数中)。
玩家A开始游戏,当两个列表都为空时游戏停止。如果游戏结束时 A 和 B 的得分都处于最佳状态,请找出 A 和 B 的得分之差。
两名玩家之间的最佳游戏意味着两名玩家都选择最佳策略来为自己实现最佳结果。在这个问题中,它意味着每个玩家每次采取行动,最大化他的分数和对手分数之间的最终差异,知道对手也在做同样的事情。
输入
输入的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100\,000$$$) — 列表的大小。
第二行包含$$$n$$$整数$$$a_i$$$ ($$$1 \le a_i \le 10^6$$$),描述开始游戏的玩家A的列表。
第三行包含$$$n$$$整数$$$b_i$$$ ($$$1 \le b_i \le 10^6$$$),描述玩家B的列表。
输出
如果 A 和 B 都处于最佳状态,则输出 A 和 B 的分数之间的差值 ($$$A-B$$$)。
示例
输入 #1
2 1 4 5 1
输出 #1
0
输入 #2
3 100 100 100 100 100 100
输出 #2
0
输入 #3
2 2 1 5 6
输出 #3
-3
注意
在第一个示例中,游戏可能如下所示:
- A 从 B 的列表中删除 $$$5$$$。
- B 从 A 的列表中删除 $$$4$$$。
- A拿走了他的$$$1$$$。
- B 拿走了他的 $$$1$$$。
因此,A 的得分为 $$$1$$$,B 的得分为 $$$1$$$,差值为 $$$0$$$。
还有另一种最佳玩法:
- A 从 B 的列表中删除 $$$5$$$。
- B 从 A 的列表中删除 $$$4$$$。
- A 从 B 的列表中删除 $$$1$$$。
- B 从 A 的列表中删除 $$$1$$$。
分数差异仍然是$$$0$$$。
在第二个示例中,无论玩家采取何种动作,他们最终都会在得分中添加相同数量的数字,因此差异将为 $$$0$$$。