#3158. 「NOI2019」序列

内存限制:512 MiB 时间限制:1000 ms 输入文件:sequence.in 输出文件:sequence.out
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

给定两个长度为 n 的正整数序列 \{a_i\} \{b_i\} ,序列的下标为 1, 2, \ldots , n 。现在你需要分别对两个序列各指定恰好 K 个下标,要求至少 L 个下标在两个序列中都被指定,使得这 2K 个下标在序列中对应的元素的总和最大

形式化地说,你需要确定两个长度为 K 的序列 \{c_i\}, \{d_i\} ,其中

1 \le c_1 < c_2 < \ldots < c_K \le n , 1 \le d_1 < d_2 < \ldots < d_K \le n

并要求

\Big| \{c_1, c_2, \ldots , c_K\} \cap \{d_1, d_2, \ldots , d_K\} \Big| \ge L

目标是最大化

\sum_{i=1}^K a_{c_i}+\sum_{i=1}^K b_{d_i}

输入格式

从文件 sequence.in 中读入数据。

本题输入文件包含多组数据。

第一行一个正整数 T 表示数据组数。接下来每三行表示一组数据。

每组数据第一行三个整数 n, K, L ,变量意义见题目描述。

每组数据第二行 n 个整数表示序列 \{a_i\}

每组数据第三行 n 个整数表示序列 \{b_i\}

输出格式

输出到文件 sequence.out 中。

对于每组数据输出一行一个整数表示答案。

样例

样例输入 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

样例输出 1

14
12
27
45
62

样例说明 1

第一组数据选择的下标为: \{c_i\} = \{1\}, \{d_i\} = \{1\}
第二组数据选择的下标为: \{c_i\} = \{1 , 3\} ,\{d_i\} = \{2,3\}
第三组数据选择的下标为: \{c_i\} = \{3, 4\} , \{d_i\} = \{3,5\}
第四组数据选择的下标为: \{c_i\} = \{2, 3, 4, 6\} , \{d_i\} = \{2,3, 4, 6\}
第五组数据选择的下标为: \{c_i\} = \{2 ,3, 4, 5, 6\} , \{d_i\} = \{1,2, 3, 4, 6\}

样例 2

见选手目录下的 sequence/sequence2.insequence/sequence2.ans

样例 3

见选手目录下的 sequence/sequence3.insequence/sequence3.ans

数据范围与提示

对于所有测试点: 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

每个测试点的具体限制见下表:

测试点编号 n\le \sum n\le
1\sim 3 10 3\times 10^5
4,5 18
6,7 30
8\sim 10 150
11\sim 16 2\times 10^3
17\sim 21 2\times 10^5
22\sim 25 10^6