← 返回题目列表

Codeforces · 2051/E

E. 最优惠价格

中文机器翻译题面 查看原题

一批圣诞树已抵达伯兰最大的商店。 $$$n$$$ 顾客已经来到商店想要购买。

在销售开始之前,商店需要确定一棵树的价格(所有顾客的价格相同)。为此,商店拥有每个顾客的一些信息。

对于第 $$$i$$$ 个客户,已知两个整数 $$$a_i$$$ 和 $$$b_i$$$,它们定义了他们的行为:

- 如果产品的价格最多为 $$$a_i$$$,客户将购买一棵树并留下正面评价;
- 否则,如果产品的价格最多为 $$$b_i$$$,客户将购买一棵树,但留下负面评论;
- 否则,客户根本不会购买一棵树。

您的任务是计算商店可能获得的最大收入,假设该商店收到的负面评论不超过 $$$k$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$0 \le k \le n$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^9$$$)。

第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 2 \cdot 10^9$$$; $$$a_i < b_i$$$)。

对输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 - 商店的最大可能收入,假设它可以收到不超过 $$$k$$$ 的负面评论。

示例

输入 #1

5
2 0
2 1
3 4
1 1
2
5
3 3
1 5 2
3 6 4
4 3
2 3 2 8
3 7 3 9
3 1
2 9 5
12 14 9

输出 #1

2
5
9
14
15

注意

考虑以下语句中的示例:

- 在第一个测试用例中,价格应设置为 $$$1$$$。然后两个顾客都会各买一棵树,并且不会留下任何负面评论;
- 在第二个测试用例中,价格应设置为 $$$5$$$。然后唯一的顾客会购买一棵树并留下负面评论;
- 在第三个测试用例中,价格应设置为 $$$3$$$。那么所有顾客都会每人购买一棵树,商店就会收到两条负面评论。
- 在第四个测试用例中,价格应设置为 $$$7$$$。然后两个顾客每人购买一棵树,商店就会收到一条负面评论。