Sequence
시간 제한1초메모리 제한512 MB
배열 a와 b에서 길이 K인 증가하는 인덱스 수열을 각각 골라 최소 L개의 인덱스를 공유하면서 선택한 값의 합이 최대가 되도록 합니다.
문제
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\ 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\).
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\).