题目描述

你是许多五颜六色手套的主人，并把它们放在一个抽屉里。每只手套都属于 $n$ 种颜色中的一种，颜色编号从 $1$ 到 $n$。 具体来说，对于每种颜色 $i$（$1 \le i \le n$），你有 $l_i$ 只左手手套和 $r_i$ 只右手手套。

不幸的是，现在是深夜，你看不见任何手套。 换句话说，你只有在把手套从抽屉里拿出来之后，才能知道它的颜色和种类（左手或右手）。

颜色为 $i$ 的一副配对手套由恰好一只左手手套和一只右手手套组成。 请你求出最少需要从抽屉中拿出多少只手套，才能保证你至少拥有 $k$ 副不同颜色的配对手套。

形式化地说，找到最小的正整数 $x$，满足：

• 无论你以何种方式拿出 $x$ 只手套，其中一定至少存在 $k$ 副不同颜色的配对手套。

输入格式

每个测试文件包含多组测试数据。 第一行一个整数 $t$（$1 \le t \le 10^4$），表示测试数据组数。

每组测试数据格式如下： 第一行两个整数 $n, k$（$1 \le k \le n \le 2 \cdot 10^5$），表示颜色数量和要求的最少配对数。 第二行 $n$ 个整数 $l_1, l_2, \dots, l_n$（$1 \le l_i \le 10^9$），表示每种颜色的左手手套数量。 第三行 $n$ 个整数 $r_1, r_2, \dots, r_n$（$1 \le r_i \le 10^9$），表示每种颜色的右手手套数量。

保证所有测试数据的 $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 种不同颜色的配对。