Given two sequences of positive integers $\{a_i\}$ and $\{b_i\}$ of length $n$, with indices $1, 2, \dots, n$. You need to select exactly $K$ indices for each of the two sequences, such that at least $L$ indices are selected in both sequences, in order to maximize the sum of the elements corresponding to these $2K$ indices.

Formally, you need to determine two sequences of length $K$, $\{c_i\}$ and $\{d_i\}$, where $$1 \le c_1 < c_2 < \dots < c_K \le n , \quad 1 \le d_1 < d_2 < \dots < d_K \le n$$ and satisfy $$|\{c_1, c_2, \dots, c_K\} \cap \{d_1, d_2, \dots, d_K\}| \ge L$$ The goal is to maximize $$\sum_{i=1}^{K} a_{c_i} + \sum_{i=1}^{K} b_{d_i}$$

Input

The input contains multiple test cases. The first line contains a positive integer $T$, representing the number of test cases. Each test case consists of three lines. The first line of each test case contains three integers $n, K, L$, with meanings as described above. The second line of each test case contains $n$ integers representing the sequence $\{a_i\}$. The third line of each test case contains $n$ integers representing the sequence $\{b_i\}$.

Output

For each test case, output a single integer on a new line representing the answer.

Examples

Input 1

5
1 1 1
7
7
3 2 1
4 1 2
1 4 2
5 2 1
4 5 5 8 4
2 1 7 2 7
6 4 1
1 5 8 3 2 4
2 6 9 3 1 7
7 5 4
1 6 6 6 5 9 1
9 5 3 9 1 4 2

Output 1

14
12
27
45
62

Note

For the first test case, the chosen indices are: $\{c_i\} = \{1\}, \{d_i\} = \{1\}$. For the second test case, the chosen indices are: $\{c_i\} = \{1, 3\}, \{d_i\} = \{2, 3\}$. For the third test case, the chosen indices are: $\{c_i\} = \{3, 4\}, \{d_i\} = \{3, 5\}$. For the fourth test case, the chosen indices are: $\{c_i\} = \{2, 3, 4, 6\}, \{d_i\} = \{2, 3, 4, 6\}$. For the fifth test case, the chosen indices are: $\{c_i\} = \{2, 3, 4, 5, 6\}, \{d_i\} = \{1, 2, 3, 4, 6\}$.

Examples

Input 2

See sequence/sequence2.in in the contestant directory.

Output 2

See sequence/sequence2.ans in the contestant directory.

Input 3

See sequence/sequence3.in in the contestant directory.

Output 3

See sequence/sequence3.ans in the contestant directory.

Constraints

For all test cases: $T \le 10$, $1 \le \sum n \le 10^6$, $1 \le L \le K \le n \le 2 \times 10^5$, $1 \le a_i, b_i \le 10^9$. The specific constraints for each test case are shown in the table below: