← Home
write a go solution for B. Wonderful Glovestime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou 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. InputEach test contains multiple test cases. The first line contains the number of test cases t (1<=t<=10^4). The description of the test cases follows. The first line of each test case contains two integers n, k (1<=k<=n<=2*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<=l_i<=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<=qr_i<=q10^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*10^5.OutputFor each test case, output a single integer — the minimum number of gloves you need to take out of the drawer.ExampleInput53 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 15Output6
101
303
481
1010
NoteIn 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.. Output only the code with no comments, explanation, or additional text.