CF2096B Wonderful Gloves

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.

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 $ .

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

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.