你是许多彩色手套的骄傲拥有者,你把它们放在抽屉里。每只手套均采用 $$$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$$$。
输出
对于每个测试用例,输出一个整数 - 您需要从抽屉中取出的手套的最小数量。
示例
输入复制
53 31 1 11 1 11 110013 2100 1 1200 1 15 297 59 50 87 3695 77 33 13 7410 697 59 50 87 36 95 77 33 13 7491 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$$$ 不同颜色的配对手套。