310962: CF1914E1. Game with Marbles (Easy Version)

E1. Game with Marbles (Easy Version)time limit per test3.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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.

Output

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

ExampleInput

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

Output

1
-9
2999999997
8
-6

Note

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.

题目大意：
这个问题的简单和困难版本的区别仅在于测试用例数量和n的约束上。在简单版本中，测试用例的数量不超过10^3，n不超过6。

爱丽丝和鲍勃最近分别从他们的父母那里得到了n种不同颜色的弹珠。爱丽丝得到了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之间。

经过讨论，爱丽丝和鲍勃提出了以下游戏：玩家轮流进行，从爱丽丝开始。在他们的回合中，一个玩家选择一个颜色i，使得两个玩家都至少有一个该颜色的弹珠。然后这个玩家丢弃一个颜色i的弹珠，他的对手丢弃所有颜色i的弹珠。当没有颜色i使得两个玩家都至少有一个该颜色的弹珠时，游戏结束。

游戏得分是爱丽丝剩下的弹珠数量和鲍勃剩下的弹珠数量之间的差值。换句话说，游戏得分等于(A-B)，其中A是游戏结束时爱丽丝拥有的弹珠数量，B是游戏结束时鲍勃拥有的弹珠数量。爱丽丝想要最大化得分，而鲍勃想要最小化得分。

如果两个玩家都采取最优策略，计算游戏结束时的得分。

输入输出数据格式：
输入：
第一行包含一个整数t（1≤t≤10^3）——测试用例的数量。
每个测试用例由三行组成：
- 第一行包含一个整数n（2≤n≤6）——颜色的数量；
- 第二行包含n个整数a_1, a_2, ..., a_n（1≤a_i≤10^9），其中a_i是爱丽丝拥有的第i种颜色的弹珠数量；
- 第三行包含n个整数b_1, b_2, ..., b_n（1≤b_i≤10^9），其中b_i是鲍勃拥有的第i种颜色的弹珠数量。

输出：
对于每个测试用例，输出一个整数——如果爱丽丝和鲍勃都采取最优策略，游戏结束时的得分。题目大意： 这个问题的简单和困难版本的区别仅在于测试用例数量和n的约束上。在简单版本中，测试用例的数量不超过10^3，n不超过6。 爱丽丝和鲍勃最近分别从他们的父母那里得到了n种不同颜色的弹珠。爱丽丝得到了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之间。 经过讨论，爱丽丝和鲍勃提出了以下游戏：玩家轮流进行，从爱丽丝开始。在他们的回合中，一个玩家选择一个颜色i，使得两个玩家都至少有一个该颜色的弹珠。然后这个玩家丢弃一个颜色i的弹珠，他的对手丢弃所有颜色i的弹珠。当没有颜色i使得两个玩家都至少有一个该颜色的弹珠时，游戏结束。 游戏得分是爱丽丝剩下的弹珠数量和鲍勃剩下的弹珠数量之间的差值。换句话说，游戏得分等于(A-B)，其中A是游戏结束时爱丽丝拥有的弹珠数量，B是游戏结束时鲍勃拥有的弹珠数量。爱丽丝想要最大化得分，而鲍勃想要最小化得分。 如果两个玩家都采取最优策略，计算游戏结束时的得分。 输入输出数据格式： 输入： 第一行包含一个整数t（1≤t≤10^3）——测试用例的数量。 每个测试用例由三行组成： - 第一行包含一个整数n（2≤n≤6）——颜色的数量； - 第二行包含n个整数a_1, a_2, ..., a_n（1≤a_i≤10^9），其中a_i是爱丽丝拥有的第i种颜色的弹珠数量； - 第三行包含n个整数b_1, b_2, ..., b_n（1≤b_i≤10^9），其中b_i是鲍勃拥有的第i种颜色的弹珠数量。 输出： 对于每个测试用例，输出一个整数——如果爱丽丝和鲍勃都采取最优策略，游戏结束时的得分。