310707: CF1874A. Jellyfish and Game

A. 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和Gellyfish玩一个游戏，Jellyfish有n个绿苹果，每个苹果有一个价值a_i，Gellyfish有m个绿苹果，每个苹果有一个价值b_i。游戏进行k轮，每轮中，奇数轮Jellyfish可以选择交换一个苹果或者什么都不做，偶数轮Gellyfish可以选择交换一个苹果或者什么都不做。两个玩家都想要最大化自己苹果的价值总和。要求计算经过k轮游戏后，Jellyfish的苹果价值总和。

**输入数据格式：**
第一行包含一个整数t，表示测试用例的数量（1≤t≤2000）。
每个测试用例包含三行：
- 第一行包含三个整数n、m和k（1≤n,m≤50，1≤k≤10^9），分别表示Jellyfish和Gellyfish的苹果数量和游戏轮数。
- 第二行包含n个整数a_1, a_2, ..., a_n（1≤a_i≤10^9），表示Jellyfish的苹果价值。
- 第三行包含m个整数b_1, b_2, ..., b_m（1≤b_i≤10^9），表示Gellyfish的苹果价值。

**输出数据格式：**
对于每个测试用例，输出一个整数，表示经过k轮游戏后，Jellyfish的苹果价值总和。

**示例：**
输入：
```
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
```
输出：
```
6
1
19
2
```**题目大意：** Jellyfish和Gellyfish玩一个游戏，Jellyfish有n个绿苹果，每个苹果有一个价值a_i，Gellyfish有m个绿苹果，每个苹果有一个价值b_i。游戏进行k轮，每轮中，奇数轮Jellyfish可以选择交换一个苹果或者什么都不做，偶数轮Gellyfish可以选择交换一个苹果或者什么都不做。两个玩家都想要最大化自己苹果的价值总和。要求计算经过k轮游戏后，Jellyfish的苹果价值总和。 **输入数据格式：** 第一行包含一个整数t，表示测试用例的数量（1≤t≤2000）。 每个测试用例包含三行： - 第一行包含三个整数n、m和k（1≤n,m≤50，1≤k≤10^9），分别表示Jellyfish和Gellyfish的苹果数量和游戏轮数。 - 第二行包含n个整数a_1, a_2, ..., a_n（1≤a_i≤10^9），表示Jellyfish的苹果价值。 - 第三行包含m个整数b_1, b_2, ..., b_m（1≤b_i≤10^9），表示Gellyfish的苹果价值。 **输出数据格式：** 对于每个测试用例，输出一个整数，表示经过k轮游戏后，Jellyfish的苹果价值总和。 **示例：** 输入： ``` 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 ``` 输出： ``` 6 1 19 2 ```