Jellyfish 拥有 $n$ 个绿苹果，价值分别为 $a_1, a_2, \dots, a_n$，Gellyfish 拥有 $m$ 个绿苹果，价值分别为 $b_1, b_2, \dots, b_m$。

他们将进行 $k$ 轮游戏。对于 $i = 1, 2, \dots, k$，他们将按此顺序执行以下操作：

• 如果 $i$ 是奇数，Jellyfish 可以选择将她的一个苹果与 Gellyfish 的一个苹果交换，或者什么都不做。
• 如果 $i$ 是偶数，Gellyfish 可以选择将他的一个苹果与 Jellyfish 的一个苹果交换，或者什么都不做。

双方都希望最大化各自苹果的价值总和。

由于你是世界上最聪明的人之一，Jellyfish 希望你告诉她，在 $k$ 轮游戏结束后，她拥有的苹果价值总和是多少。假设 Jellyfish 和 Gellyfish 都采取最优策略以最大化各自苹果的价值总和。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 2000$)。接下来是测试用例的描述。

每个测试用例的第一行包含三个整数 $n, m$ 和 $k$ ($1 \le n, m \le 50, 1 \le k \le 10^9$)，分别表示 Jellyfish 拥有的绿苹果数量、Gellyfish 拥有的绿苹果数量以及游戏轮数。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$)，表示 Jellyfish 绿苹果的价值。

每个测试用例的第三行包含 $m$ 个整数 $b_1, b_2, \dots, b_m$ ($1 \le b_i \le 10^9$)，表示 Gellyfish 绿苹果的价值。

注意，$n$ 和 $m$ 的总和在所有测试用例中均无限制。

输出格式

对于每个测试用例，输出一个整数，即 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 会交换价值为 1 和 4 的苹果。 在第二个测试用例中，双方会将这两个苹果交换 10,000 次。 在第四个测试用例中，Jellyfish 什么都不会做。