Problem Description

Given two positive integer sequences $\{a_i\}$ and $\{b_i\}$ of length $n$, where the indices are $1, 2, \cdots , n$. You now need to choose exactly $K$ indices for each sequence, requiring that at least $L$ indices are chosen in both sequences, so that the total sum of the corresponding elements of these $2K$ indices is maximized.

Formally, you need to determine two sequences $\{c_i\}$ and $\{d_i\}$ of length $K$, where $1 \leq c_1 < c_2 < \cdots < c_K \leq n , 1 \leq d_1 < d_2 < \cdots < d_K \leq n$

and require that $\left \lvert \{c_1, c_2, \cdots , c_K\} \cap \{d_1, d_2, · · · , d_K\} \right \rvert \geq L$.

The goal is to maximize $\sum^{K}_{i=1} a_{c_i} +\sum^{K}_{i=1} b_{d_i}$.

Input Format

This input file contains multiple test cases.

The first line contains a positive integer $T$ indicating the number of test cases. Then every three lines describe one test case.

For each test case, the first line contains three integers $n, K, L$, with meanings as described in the statement.

For each test case, the second line contains $n$ integers representing the sequence $\{a_i\}$.

For each test case, the third line contains $n$ integers representing the sequence $\{b_i\}$.

Output Format

For each test case, output one line containing one integer, the answer.

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

14
12
27
45
62

Hint

More Samples

You can get more samples from the additional files.

Sample 2

See sequence/sequence2.in and sequence/sequence2.ans in the contestant directory.

Sample 3

See sequence/sequence3.in and sequence/sequence3.ans in the contestant directory.

Explanation for Sample 1

In the first test case, the chosen indices are: $\{c_i\} = \{1\} , \{d_i\} = \{1\}$.

In the second test case, the chosen indices are: $\{c_i\} = \{1, 3\} , \{d_i\} = \{2, 3\}$.

In the third test case, the chosen indices are: $\{c_i\} = \{3, 4\} , \{d_i\} = \{3, 5\}$.

In the fourth test case, the chosen indices are: $\{c_i\} = \{2, 3, 4, 6\} , \{d_i\} = \{2, 3, 4, 6\}$.

In the fifth test case, the chosen indices are: $\{c_i\} = \{2, 3, 4, 5, 6\} , \{d_i\} = \{1, 2, 3, 4, 6\}$.

Constraints

For all test points: $T \leq 10 , 1 \leq \sum n \leq 10^6, 1 \leq L \leq K \leq n \leq 2 \times 10^5, 1 \leq a_i, b_i \leq 10^9$.

::cute-table{tuack}

Translated by ChatGPT 5