← 返回题目列表

Codeforces · 2096/B

B. 很棒的手套

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

你是许多彩色手套的骄傲拥有者,你把它们放在抽屉里。每只手套均采用 $$$n$$$ 颜色之一,编号为 $$$1$$$ 至 $$$n$$$。具体来说,对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$i$$$,您都有 $$$l_i$$$ 左手套和 $$$r_i$$$ 右手套,颜色为 $$$i$$$。

可惜现在已经是深夜了,所以 你看不到任何手套。换句话说,您只会知道手套的颜色和类型(左或右) 之后 你把它从抽屉里拿出来。

一副颜色为 $$$i$$$ 的匹配手套由一只左手套和一只右手套组成,颜色为 $$$i$$$。找出您需要从抽屉中取出的最少手套数量 保证 你有 至少 $$$k$$$ 配对手套 不同 颜色。

正式地,找到最小的正整数 $$$x$$$ 使得:

  • 对于您从抽屉中取出的任何一套 $$$x$$$ 手套,总会有至少 $$$k$$$ 匹配的不同颜色的手套。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$、$$$k$$$ ($$$1 \leq k \leq n \leq 2 \cdot 10^5$$$) - 不同颜色的数量,以及所需匹配手套的最小数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$l_1, l_2, \ldots, l_n$$$ ($$$1 \leq l_i \leq 10^9$$$) - 从 $$$1$$$ 到 $$$n$$$ 的每个 $$$i$$$ 颜色为 $$$i$$$ 的左手套数量。

每个测试用例的第三行包含 $$$n$$$ 整数 $$$r_1, r_2, \ldots, r_n$$$ ($$$1 \leq r_i \leq 10^9$$$) - 每个 $$$i$$$ 从 $$$1$$$ 到 $$$n$$$ 的颜色为 $$$i$$$ 的右手套数量。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数 - 您需要从抽屉中取出的手套的最小数量。

示例

输入
复制

5
3 3
1 1 1
1 1 1
1 1
100
1
3 2
100 1 1
200 1 1
5 2
97 59 50 87 36
95 77 33 13 74
10 6
97 59 50 87 36 95 77 33 13 74
91 14 84 33 54 89 68 34 14 15

输出
复制

6
101
303
481
1010

注意

在第一个测试用例中,您必须取出所有手套,因此答案是 $$$6$$$。

在第二个测试用例中,答案是 $$$101$$$。如果您取出 $$$100$$$ 或更少的手套,那么很可能所有手套都是左手套,这意味着您将没有一双匹配的手套。

在第三个测试用例中,答案是 $$$303$$$。如果你只拿出$$$302$$$手套,那么一种可能的情况如下:

  • 颜色 $$$1$$$:$$$100$$$ 左手套,$$$200$$$ 右手套
  • 颜色 $$$2$$$:$$$1$$$ 左手套,$$$0$$$ 右手套
  • 颜色 $$$3$$$:$$$0$$$ 左手套,$$$1$$$ 右手套

您只有多副颜色为 $$$1$$$ 的匹配手套。因此,您不会有至少 $$$2$$$ 不同颜色的配对手套。