sequence_loj

Sequence

There are two sequences of positive integers $\{a_i\}$ and $\{b_i\}$, each containing $n$ elements indexed $1$ to $n$. You are to choose $K$ integers from each sequence, out of which there must be at least $L$ indices which are chosen in both sequences. Given these requirements, choose these $2K$ integers such that their sum is maximized.

Formally, you are to choose two sets $\{c_i\}$ and $\{d_i\}$ of size K such that

• $1\le c_1<c_2<\dots <c_K\le n$
• $1\le d_1<d_2<\dots <d_K\le n$
• $|\{c_1,c_2,\dots ,c_K\}\cap \{d_1,d_2,\dots ,d_K\}|\ge L$

Your task is then to maximize $\sum _{i=1}^K{a}_{c_i}+\sum _{i=1}^K{b}_{d_i}$.

Input format

The first line of input consists of a single integer $T$, the number of testcases.

$T$ testcases will follow. Each test case consists of 3 lines.

The first line of each testcase will contain 3 integers, $n$, $K$, and $L$.

The second line of each testcase will contain $n$ integers $a_1,a_2,\dots ,a_n$.

The third line of each testcase will contain $n$ integers $b_1,b_2,\dots ,b_n$.

Output format

Output one line for each testcase, each containing a single integer - the maximum sum of elements as described.

Limits

$1\le 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$.

Subtask #	Score	Constraints
1	12	$n\le 10$
2	8	$n\le 18$
3	8	$n\le 30$
4	12	$n\le 150$
5	24	$n\le 2000$
6	20	$\sum n\le 3\times {10}^5$
7	16	No additional constraints

Samples

Sample Input 1	Sample Output 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	14 12 27 45 62

The optimal solution for the first testcase is $\{c_i\}=\{d_i\}=\{1\}$.
An optimal solution for the second testcase is $\{c_i\}=\{1,3\},\{d_i\}=\{2,3\}$.
The optimal solution for the third testcase is $\{c_i\}=\{3,4\},\{d_i\}=\{3,5\}$.
The optimal solution for the fourth testcase is $\{c_i\}=\{d_i\}=\{2,3,4,6\}$.
The optimal solution for the fifth testcase is $\{c_i\}=\{2,3,4,5,6\},\{d_i\}=\{1,2,3,4,6\}$.