CF1914E1.Game with Marbles (Easy Version)

The easy and hard versions of this problem differ only in the constraints on the number of test cases and $n$. In the easy version, the number of test cases does not exceed $10^3$, and $n$ does not exceed $6$.

Recently, Alice and Bob were given marbles of $n$ different colors by their parents. Alice has received $a_1$ marbles of color $1$, $a_2$ marbles of color $2$,..., $a_n$ marbles of color $n$. Bob has received $b_1$ marbles of color $1$, $b_2$ marbles of color $2$, ..., $b_n$ marbles of color $n$. All $a_i$ and $b_i$ are between $1$ and $10^9$.

After some discussion, Alice and Bob came up with the following game: players take turns, starting with Alice. On their turn, a player chooses a color $i$ such that both players have at least one marble of that color. The player then discards one marble of color $i$, and their opponent discards all marbles of color $i$. The game ends when there is no color $i$ such that both players have at least one marble of that color.

The score in the game is the difference between the number of remaining marbles that Alice has and the number of remaining marbles that Bob has at the end of the game. In other words, the score in the game is equal to $(A-B)$, where $A$ is the number of marbles Alice has and $B$ is the number of marbles Bob has at the end of the game. Alice wants to maximize the score, while Bob wants to minimize it.

Calculate the score at the end of the game if both players play optimally.

本题的简单版本与困难版本仅在测试用例数量和 $n$ 的约束上有所不同。在简单版本中，测试用例数量不超过 $10^3$，且 $n$ 不超过 $6$。

最近，Alice 和 Bob 从父母那里收到了 $n$ 种不同颜色的弹珠。Alice 收到了颜色 $1$ 的弹珠 $a_1$ 颗、颜色 $2$ 的弹珠 $a_2$ 颗、……、颜色 $n$ 的弹珠 $a_n$ 颗；Bob 收到了颜色 $1$ 的弹珠 $b_1$ 颗、颜色 $2$ 的弹珠 $b_2$ 颗、……、颜色 $n$ 的弹珠 $b_n$ 颗。所有 $a_i$ 和 $b_i$ 均在 $1$ 到 $10^9$ 之间。

经过一番讨论，Alice 和 Bob 设计了如下游戏：两人轮流进行，Alice 先手。在每一轮中，当前玩家选择一种颜色 $i$，要求双方在该颜色上均至少拥有一颗弹珠。然后，当前玩家丢弃一颗颜色 $i$ 的弹珠，而其对手则丢弃所有颜色 $i$ 的弹珠。当不存在任何颜色 $i$ 满足双方在该颜色上均至少拥有一颗弹珠时，游戏结束。

游戏的得分为游戏结束时 Alice 剩余弹珠数与 Bob 剩余弹珠数之差。换言之，游戏得分为 $(A-B)$，其中 $A$ 表示游戏结束时 Alice 拥有的弹珠数，$B$ 表示 Bob 拥有的弹珠数。Alice 希望最大化该得分，而 Bob 希望最小化该得分。

若双方均采取最优策略，请计算游戏结束时的得分。

The first line contains a single integer $t$ ($1 \le t \le 10^3$) — the number of test cases.

Each test case consists of three lines:

• the first line contains a single integer $n$ ($2 \le n \le 6$) — the number of colors;
• the second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), where $a_i$ is the number of marbles of the $i$-th color that Alice has;
• the third line contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_i \le 10^9$), where $b_i$ is the number of marbles of the $i$-th color that Bob has.

第一行包含一个整数 $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$ 种颜色的弹珠数量。

For each test case, output a single integer — the score at the end of the game if both Alice and Bob act optimally.

对于每个测试用例，输出一个整数——即在 Alice 和 Bob 均采取最优策略的情况下，游戏结束时的得分。

In the first example, one way to achieve a score of $1$ is as follows:

1. Alice chooses color $1$, discards $1$ marble. Bob also discards $1$ marble;
2. Bob chooses color $3$, discards $1$ marble. Alice also discards $1$ marble;
3. Alice chooses color $2$, discards $1$ marble, and Bob discards $2$ marble.

As a result, Alice has $a = [3, 1, 0]$ remaining, and Bob has $b = [0, 0, 3]$ remaining. The score is $3 + 1 - 3 = 1$.

It can be shown that neither Alice nor Bob can achieve a better score if both play optimally.

In the second example, Alice can first choose color $1$, then Bob will choose color $4$, after which Alice will choose color $2$, and Bob will choose color $3$. It can be shown that this is the optimal game.

在第一个例子中，一种得到分数 $1$ 的方法如下：

1. 爱丽丝选择颜色 $1$，丢弃 $1$ 颗弹珠；鲍勃也丢弃 $1$ 颗弹珠；
2. 鲍勃选择颜色 $3$，丢弃 $1$ 颗弹珠；爱丽丝也丢弃 $1$ 颗弹珠；
3. 爱丽丝选择颜色 $2$，丢弃 $1$ 颗弹珠，而鲍勃丢弃 $2$ 颗弹珠。

最终，爱丽丝剩余的弹珠为 $a = [3, 1, 0]$，鲍勃剩余的弹珠为 $b = [0, 0, 3]$。得分为 $3 + 1 - 3 = 1$。

可以证明：若双方均采取最优策略，则谁都无法获得更高的分数。

在第二个例子中，爱丽丝可先选择颜色 $1$，随后鲍勃将选择颜色 $4$，接着爱丽丝选择颜色 $2$，鲍勃再选择颜色 $3$。可以证明这是最优的游戏过程。