CF2238A Another Puzzle from Papyrus

You are filled with determination. — Undertale Papyrus came up with another puzzle for Frisk to solve. Papyrus brought two arrays $ a $ and $ b $ of length $ n $ and allowed the following two operations to be performed: - choose any index $ i $ ( $ 1 \le i \le n $ ) and change $ a_i $ to $ a_i - 1 $ . The execution time of such an operation is $ 1 $ second. - reorder all elements of array $ a $ in any way. The execution time of such an operation is $ c $ seconds. You need to convert array $ a $ into array $ b $ . Frisk wants to solve the puzzle as soon as possible. Help Frisk determine the minimum time needed to solve the puzzle. If there is no solution, output $ -1 $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 500 $ ). The description of the test cases follows. The first line of each test case contains two integers $ n $ and $ c $ ( $ 1 \le n, c \le 100 $ ) — the length of arrays $ a $ and $ b $ and the cost of the second operation. The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 100 $ ) — the elements of the first array. The third line of each test case contains $ n $ integers $ b_1, b_2, \ldots, b_n $ ( $ 1 \le b_i \le 100 $ ) — the elements of the second array.

For each test case, output a single integer representing the minimum number of seconds required to solve the puzzle, or $ -1 $ if it is impossible to solve the puzzle.

In the first test case, it is impossible to transform $ a $ into $ b $ using only subtraction because $ a_2 \lt b_2 $ . Let's rearrange the elements of array $ a $ as follows: $ [5, 2, 3] \Rightarrow [2, 3, 5] $ . Now it is enough to subtract one from $ a_3 $ , and we get that array $ a $ becomes equal to array $ b $ in $ 5 + 1 = 6 $ seconds. In the second test case, all elements of $ a $ are less than all elements of $ b $ , which means $ a $ cannot be transformed into $ b $ . In the third test case, you can choose not to rearrange the elements and get an answer of $ 3 $ . If you rearrange them at least once, the answer will be at least $ 4 $ , so the optimal answer is $ 3 $ seconds. In the sixth test case, the array can be rearranged as follows: $ [14, 20, 20] $ . It can be seen that the cost will then be $ 5 + (14 - 12) + (20 - 18) + (20 - 17) = 12 $ .