题目描述

给定两个长度为 $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{ci}+\sum{i=1}^K b_{d_i} $$

输入格式

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

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

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

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

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

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

输出格式

输出到文件 sequence.out 中。

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

样例

input

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

output

14
12
27
45
62

第一组数据选择的下标为： ${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}$。

见选手目录下的 sequence/sequence2.in 与 sequence/sequence2.ans。

见选手目录下的 sequence/sequence3.in 与 sequence/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$。

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