You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小 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 想让你求出：她最少花费多少元才能购买恰好 $k$ 件商品。

输入格式

本题单个测试点内有多组测试数据。 输入的第一行是一个整数，表示数据组数 $T$。对每组数据，按如下格式输入：

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

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

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

输出格式

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

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

6
8
6

提示

样例解释

• 对第一组数据，选择第 $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$。

数据范围

对于 $15\%$ 的数据，$k = 1$。

对于 $35\%$ 的数据，$n \leq 20$。

对于 $65\%$ 的数据，$n \leq 10^3$。

对于 $85\%$ 的数据，$n \leq 10^4,1\le k \le 1000$。

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