P5470 [NOI2019] Sequence

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}$.

**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\}$.

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

### 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} | Test Point ID | $n\le$ | $\sum n \le$ | | :----------: | :----------: | :----------: | | $1\sim3$ | $10$ | $3\times 10^5$ | | $4\sim5$ | $18$ | ^ | | $6\sim7$ | $30$ | ^ | | $8\sim10$ | $150$ | ^ | | $11\sim16$ | $2\times 10^3$ | ^ | | $17\sim21$ | $2\times 10^5$ | ^ | | $22\sim25$ | ^ | $10^6$ | Translated by ChatGPT 5