19654번 - Sequence 다국어

Given two positive integer sequences \({a_1, a_2, \dots, a_n}\) and \({b_1, b_2, \dots, b_n}\) of length \(n\), you must find two sequences \({c_1, c_2, \dots, c_K}\) and \({d_1, d_2, \dots, d_K}\) of length \(K\) satisfying the following conditions:

1. \(1\ le c_1 < c_2 < \dots < c_K \le n\).
2. \(1 \le d_1 < d_2 < \dots < d_K \le n\).
3. \(|{c_1, c_2, \dots, c_K} \cap {d_1, d_2,\dots,d_K}| \ge L\).

Subject to these conditions, maximize \(\sum_{i=1}^{K}{a_{c_i}} + \sum_{i=1}^{K}{b_{d_i}}\).

The first line contains an integer \(T\), indicating the number of testcases.

For each testcase:

The first line contains three integers \(n, K, L\).

The second line contains \(n\) integers, indicating \({a_1, a_2, \dots, a_n}\).

The third line contains \(n\) integers, indicating \({b_1, b_2, \dots, b_n}\).

Output one integer on one line, the answer.

For all test cases, \(T \le 10, 1 \le \sigma{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\).