该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

新赛道的小$W$ 今天来到了苏州外国语学校的超市。

这个超市有 $n$ 件商品，第 $i$ 件商品有两个价格参数 $a_i$，$b_i$

小$W$ 将会从 $n$ 件商品中挑选出恰好 $k$ 件商品。在付款的时候，小$W$需要支付的金额是这 $k$ 件商品参数 $a_i$ 之和加上参数 $b_i$ 的最大值。

更形式化的说明：

假设小$W$ 选择的商品下标是 $p_1, p_2, \dots p_k(1 \leq p_1 < p_2 < \dots < p_k \leq n)$，他需要支付的金额是：

只有购买 $k$ 件商品，小$W$才能从这个商店离开。小$W$ 想让你求出：他最少花费多少元才能购买恰好 $k$ 件商品。

输入格式

**本题单个测试点内有多组测试数据。**输入的第一行是一个整数，表示数据组数 $T$。

对每组数据，按如下格式输入：

第一行是两个整数，依次表示商品个数 $n$ 和应挑选的商品数量 $k$。

第二行有 $n$ 个整数，第 $i$ 个整数表示 $a_i$。

第三行有 $n$ 个整数，第 $i$ 个整数表示 $b_i$。

输出格式

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

样例1输入

3
3 2
1 2 3
3 2 1
5 3
1 1 1 2 3
5 4 3 2 1
3 2
1 2 3
100 1 1

样例1输出

6
8
6

样例2输入

2
4 2
1 7 2 5
2 3 5 6
5 1
1 2 3 4 5
5 4 3 2 1

样例2输出

8
6

样例3输入

见考生文件夹中的下发大样例buy3.in

样例3输出

见考生文件夹中的下发大样例buy3.out

提示/说明

样例1解释

• 对第一组数据，选择第 $1, 2$ 件商品。花费为 $(1 + 2) + \max\{3, 2\} = 3 + 3 = 6$。
• 对第二组数据，选择第 $2,3,4$ 件商品，花费为 $(1 + 1 + 2) + \max\{4, 3, 2\} = 4 + 4 = 8$。
• 对第三组数据，选择第 $2, 3$ 件商品，花费为 $(2 + 3) + \max\{1, 1\} = 5 + 1 = 6$。

数据范围

对于 $100\%$ 的数据，$1 \leq k \leq n \leq 10^6$，$1 \leq a_i, b_i \leq 10^{12}$，$1 \leq T \leq 3$。