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 \leq c_1 < c_2 < \ldots < c_K \leq n\)
• \(1 \leq d_1 < d_2 < \ldots < d_K \leq n\)
• \(|\{c_1, c_2, \ldots, c_K\} \cap \{d_1, d_2, \ldots, d_K\}| \geq 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, \ldots, a_n\).

The third line of each testcase will contain \(n\) integers \(b_1, b_2, \ldots, b_n\).

Output format

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

Limits

\(1 \leq 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\).

Subtask #	Score	Constraints
1	12	\(n \leq 10\)
2	8	\(n \leq 18\)
3	8	\(n \leq 30\)
4	12	\(n \leq 150\)
5	24	\(n \leq 2000\)
6	20	\(\sum{n} \leq 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\}\).