这个问题的简单版本和困难版本仅在测试用例数量和 $$$n$$$ 的限制上有所不同。在简易版本中,测试用例数量不超过$$$10^3$$$,$$$n$$$不超过$$$6$$$。
最近,爱丽丝和鲍勃的父母给了他们 $$$n$$$ 不同颜色的弹珠。 Alice 收到了 $$$a_1$$$ 颜色为 $$$1$$$ 的弹珠、$$$a_2$$$ 颜色为 $$$2$$$ 的弹珠、...、$$$a_n$$$ 颜色为 $$$n$$$ 的弹珠。鲍勃收到了 $$$b_1$$$ 颜色为 $$$1$$$ 的弹珠、$$$b_2$$$ 颜色为 $$$2$$$ 的弹珠、...、$$$b_n$$$ 颜色为 $$$n$$$ 的弹珠。所有 $$$a_i$$$ 和 $$$b_i$$$ 均在 $$$1$$$ 和 $$$10^9$$$ 之间。
经过一番讨论,Alice 和 Bob 提出了以下游戏:玩家轮流,从 Alice 开始。轮到玩家时,他们选择一种颜色 $$$i$$$,这样两个玩家都至少拥有一个该颜色的弹珠。然后,玩家丢弃一颗颜色为 $$$i$$$ 的弹珠,而对手则丢弃所有颜色为 $$$i$$$ 的弹珠。当没有颜色 $$$i$$$ 且两名玩家都至少拥有一颗该颜色的弹珠时,游戏结束。
游戏中的分数是游戏结束时爱丽丝拥有的剩余弹珠数量与鲍勃拥有的剩余弹珠数量之间的差值。换句话说,游戏中的分数等于$$$(A-B)$$$,其中$$$A$$$是Alice拥有的弹珠数量,$$$B$$$是Bob在游戏结束时拥有的弹珠数量。 Alice 想要最大化分数,而 Bob 想要最小化分数。
如果双方都发挥最佳,则计算游戏结束时的得分。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^3$$$) — 测试用例的数量。
每个测试用例由三行组成:
- 第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 6$$$) — 颜色数量;
- 第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$),其中 $$$a_i$$$ 是 Alice 拥有的第 $$$i$$$ 颜色的弹珠数量;
- 第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 10^9$$$),其中 $$$b_i$$$ 是 Bob 拥有的第 $$$i$$$ 颜色的弹珠数量。
输出
对于每个测试用例,输出一个整数 - 如果 Alice 和 Bob 都表现最佳,则游戏结束时的分数。
示例
输入 #1
5 3 4 2 1 1 2 4 4 1 20 1 20 100 15 10 20 5 1000000000 1000000000 1000000000 1000000000 1000000000 1 1 1 1 1 3 5 6 5 2 1 7 6 3 2 4 2 5 5 9 4 7 9 2 5
输出 #1
1 -9 2999999997 8 -6
注意
在第一个示例中,获得 $$$1$$$ 分数的一种方法如下:
1. Alice 选择颜色 $$$1$$$,丢弃 $$$1$$$ 大理石。鲍勃还丢弃了 $$$1$$$ 大理石;
2. Bob 选择颜色 $$$3$$$,丢弃 $$$1$$$ 大理石。爱丽丝还丢弃了 $$$1$$$ 大理石;
3. Alice 选择颜色 $$$2$$$,丢弃 $$$1$$$ 大理石,Bob 丢弃 $$$2$$$ 大理石。
结果,Alice 剩余 $$$a = [3, 1, 0]$$$,Bob 剩余 $$$b = [0, 0, 3]$$$。得分为 $$$3 + 1 - 3 = 1$$$。
可以证明,如果 Alice 和 Bob 都发挥最佳,则两者都无法获得更好的分数。
在第二个例子中,Alice可以先选择颜色$$$1$$$,然后Bob会选择颜色$$$4$$$,之后Alice会选择颜色$$$2$$$,Bob会选择颜色$$$3$$$。可以证明这是最优博弈。