310715: CF1875B. Jellyfish and Game

B. Jellyfish and Gametime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Jellyfish has $n$ green apples with values $a_1, a_2, \dots, a_n$ and Gellyfish has $m$ green apples with values $b_1,b_2,\ldots,b_m$.

They will play a game with $k$ rounds. For $i=1,2,\ldots,k$ in this order, they will perform the following actions:

• If $i$ is odd, Jellyfish can choose to swap one of her apples with one of Gellyfish's apples or do nothing.
• If $i$ is even, Gellyfish can choose to swap one of his apples with one of Jellyfish's apples or do nothing.

Both players want to maximize the sum of the values of their apples.

Since you are one of the smartest people in the world, Jellyfish wants you to tell her the final sum of the value of her apples after all $k$ rounds of the game. Assume that both Jellyfish and Gellyfish play optimally to maximize the sum of values of their apples.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 2000$). The description of the test cases follows.

The first line of each test case contains three integers, $n$, $m$ and $k$ ($1 \leq n, m \leq 50$, $1 \leq k \leq 10^9$) — the number of green apples Jellyfish has, the number of green apples Gellyfish has and the number of rounds of the game respectively.

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq 10^9$) — the values of Jellyfish's green apples.

The third line of each test case contains $m$ integers $b_1, b_2, \dots, b_m$ ($1 \leq b_i \leq 10^9$) — the values of Gellyfish's green apples.

Do note that the sum of $n$ and $m$ over all test cases are both not bounded.

Output

For each test case, output a single integer — the final sum of the values of Jellyfish's apples.

ExampleInput

4
2 2 1
1 2
3 4
1 1 10000
1
2
4 5 11037
1 1 4 5
1 9 1 9 8
1 1 1
2
1

Output

6
1
19
2

Note

In the first test case, Jellyfish will swap the apple of value $1$ and $4$.

In the second test case, both players will swap the two apples $10,000$ times.

In the fourth test case, Jellyfish will do nothing.

题目大意：
Jellyfish有n个绿苹果，分别有值a_1, a_2, \ldots, a_n，Gellyfish有m个绿苹果，分别有值b_1, b_2, \ldots, b_m。他们将进行k轮游戏。对于每一轮i（i从1到k），他们将按照以下规则行动：

- 如果i是奇数，Jellyfish可以选择交换她和一个Gellyfish的苹果，或者不做任何交换。
- 如果i是偶数，Gellyfish可以选择交换他和一个Jellyfish的苹果，或者不做任何交换。

两个玩家都希望最大化自己苹果的价值总和。假设Jellyfish和Gellyfish都采取最优策略以最大化他们苹果的价值总和，求出所有k轮游戏后Jellyfish苹果的总价值。

输入数据格式：
输入包含多个测试用例。第一行包含测试用例的数量t（1 \leq t \leq 2000）。每个测试用例的描述如下：

- 第一行包含三个整数n、m和k（1 \leq n, m \leq 50，1 \leq k \leq 10^9）—— Jellyfish的绿苹果数量、Gellyfish的绿苹果数量和游戏的轮数。
- 第二行包含n个整数a_1, a_2, \ldots, a_n（1 \leq a_i \leq 10^9）—— Jellyfish的绿苹果的价值。
- 第三行包含m个整数b_1, b_2, \ldots, b_m（1 \leq b_i \leq 10^9）—— Gellyfish的绿苹果的价值。

注意，所有测试用例的n和m之和均不受限制。

输出数据格式：
对于每个测试用例，输出一个整数——所有k轮游戏后Jellyfish苹果的总价值。

示例输入输出：
```
Input
4
2 2 1
1 2
3 4
1 1 10000
1
2
4 5 11037
1 1 4 5
1 9 1 9 8
1 1 1
2
1

Output
6
1
19
2
```

注意：
- 在第一个测试用例中，Jellyfish将交换值为1和4的苹果。
- 在第二个测试用例中，两个玩家将交换两个苹果10000次。
- 在第四个测试用例中，Jellyfish将不做任何交换。题目大意： Jellyfish有n个绿苹果，分别有值a_1, a_2, \ldots, a_n，Gellyfish有m个绿苹果，分别有值b_1, b_2, \ldots, b_m。他们将进行k轮游戏。对于每一轮i（i从1到k），他们将按照以下规则行动： - 如果i是奇数，Jellyfish可以选择交换她和一个Gellyfish的苹果，或者不做任何交换。 - 如果i是偶数，Gellyfish可以选择交换他和一个Jellyfish的苹果，或者不做任何交换。 两个玩家都希望最大化自己苹果的价值总和。假设Jellyfish和Gellyfish都采取最优策略以最大化他们苹果的价值总和，求出所有k轮游戏后Jellyfish苹果的总价值。 输入数据格式： 输入包含多个测试用例。第一行包含测试用例的数量t（1 \leq t \leq 2000）。每个测试用例的描述如下： - 第一行包含三个整数n、m和k（1 \leq n, m \leq 50，1 \leq k \leq 10^9）—— Jellyfish的绿苹果数量、Gellyfish的绿苹果数量和游戏的轮数。 - 第二行包含n个整数a_1, a_2, \ldots, a_n（1 \leq a_i \leq 10^9）—— Jellyfish的绿苹果的价值。 - 第三行包含m个整数b_1, b_2, \ldots, b_m（1 \leq b_i \leq 10^9）—— Gellyfish的绿苹果的价值。 注意，所有测试用例的n和m之和均不受限制。 输出数据格式： 对于每个测试用例，输出一个整数——所有k轮游戏后Jellyfish苹果的总价值。 示例输入输出： ``` Input 4 2 2 1 1 2 3 4 1 1 10000 1 2 4 5 11037 1 1 4 5 1 9 1 9 8 1 1 1 2 1 Output 6 1 19 2 ``` 注意： - 在第一个测试用例中，Jellyfish将交换值为1和4的苹果。 - 在第二个测试用例中，两个玩家将交换两个苹果10000次。 - 在第四个测试用例中，Jellyfish将不做任何交换。