B. Wonderful Gloves
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are the proud owner of many colorful gloves, and you keep them in a drawer. Each glove is in one of $$$n$$$ colors numbered $$$1$$$ to $$$n$$$. Specifically, for each $$$i$$$ from $$$1$$$ to $$$n$$$, you have $$$l_i$$$ left gloves and $$$r_i$$$ right gloves with color $$$i$$$.

Unfortunately, it's late at night, so you can't see any of your gloves. In other words, you will only know the color and the type (left or right) of a glove after you take it out of the drawer.

A matching pair of gloves with color $$$i$$$ consists of exactly one left glove and one right glove with color $$$i$$$. Find the minimum number of gloves you need to take out of the drawer to guarantee that you have at least $$$k$$$ matching pairs of gloves with different colors.

Formally, find the smallest positive integer $$$x$$$ such that:

  • For any set of $$$x$$$ gloves you take out of the drawer, there will always be at least $$$k$$$ matching pairs of gloves with different colors.
Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$, $$$k$$$ ($$$1 \leq k \leq n \leq 2 \cdot 10^5$$$) — the number of different colors, and the minimum number of required matching pairs of gloves.

The second line of each test case contains $$$n$$$ integers $$$l_1, l_2, \ldots, l_n$$$ ($$$1 \leq l_i \leq 10^9$$$) — the number of left gloves with color $$$i$$$ for each $$$i$$$ from $$$1$$$ to $$$n$$$.

The third line of each test case contains $$$n$$$ integers $$$r_1, r_2, \ldots, r_n$$$ ($$$1 \leq r_i \leq 10^9$$$) — the number of right gloves with color $$$i$$$ for each $$$i$$$ from $$$1$$$ to $$$n$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output a single integer — the minimum number of gloves you need to take out of the drawer.

Example
Input
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
Output
6
101
303
481
1010
Note

In the first test case, you must take out all of the gloves, so the answer is $$$6$$$.

In the second test case, the answer is $$$101$$$. If you take out $$$100$$$ gloves or fewer, then it is possible that all of them are left gloves, which means you won't have a matching pair of gloves.

In the third test case, the answer is $$$303$$$. If you only take out $$$302$$$ gloves, then one possible scenario is as follows:

  • Color $$$1$$$: $$$100$$$ left gloves, $$$200$$$ right gloves
  • Color $$$2$$$: $$$1$$$ left glove, $$$0$$$ right gloves
  • Color $$$3$$$: $$$0$$$ left gloves, $$$1$$$ right glove

You only have multiple matching pairs of gloves with color $$$1$$$. So you won't have at least $$$2$$$ matching pairs of gloves with different colors.