← 返回题目列表

Codeforces · 1969/D

D. 商店游戏

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

Alice 和 Bob 正在商店里玩游戏。商店里有 $$$n$$$ 商品;每个项目都有两个参数:$$$a_i$$$(Alice 的项目价格)和 $$$b_i$$$(Bob 的项目价格)。

Alice 想要选择一个项目子集(可能为空)并购买它们。之后,Bob 执行以下操作:

- 如果Alice购买的物品少于$$$k$$$,Bob可以免费拿走所有物品;
- 否则,他将免费拿走 Alice 购买的 $$$k$$$ 物品(Bob 选择哪些 $$$k$$$ 物品),而对于其余选定的物品,Bob 将从 Alice 处购买它们,并为第 $$$i$$$ 物品支付 $$$b_i$$$ 费用。

Alice 的利润等于 $$$\sum\limits_{i \in S} b_i - \sum\limits_{j \in T} a_j$$$,其中 $$$S$$$ 是 Bob 从 Alice 处购买的商品集合,$$$T$$$ 是 Alice 从商店购买的商品集合。换句话说,爱丽丝的利润是鲍勃支付给她的金额与她购买物品所花费的金额之间的差额。

Alice 想要最大化她的利润,Bob 想要最小化 Alice 的利润。您的任务是计算爱丽丝和鲍勃都采取最佳行动时爱丽丝的利润。

输入

第一行包含一个整数 $$$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 10^9$$$)。

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

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

输出

对于每个测试用例,打印一个整数 - 如果 Alice 和 Bob 都表现最佳,则 Alice 的利润。

示例

输入 #1

4
2 0
2 1
1 2
4 1
1 2 1 4
3 3 2 3
4 2
2 1 1 1
4 2 3 2
6 2
1 3 4 9 1 3
7 6 8 10 6 8

输出 #1

1
1
0
7

注意

在第一个测试用例中,Alice 应该购买 $$$2$$$-nd 商品并将其出售给 Bob,因此她的利润为 $$$2 - 1 = 1$$$。

在第二个测试用例中,Alice 应该购买 $$$1$$$-st、$$$2$$$-nd 和 $$$3$$$-rd 商品;那么鲍勃免费拿走第 $$$1$$$-st 商品,并支付 $$$2$$$-nd 和 $$$3$$$-rd 商品。 Alice 的利润为 $$$(3+2) - (1+2+1) = 1$$$。鲍勃可以免费拿走 $$$2$$$-nd 物品;这不会改变爱丽丝的利润。 Bob 不会免费拿走 $$$3$$$-rd 商品,因为这会带来 $$$2$$$ 的利润。