Papyrus 提出了另一个需要 Frisk 解决的谜题。 Papyrus 带来了两个长度为 $$$n$$$ 的数组 $$$a$$$ 和 $$$b$$$ 并允许执行以下两个操作:
- 选择任意索引 $$$i$$$ ($$$1 \le i \le n$$$) 并将 $$$a_i$$$ 更改为 $$$a_i - 1$$$。此类操作的执行时间为 $$$1$$$ 秒。
- 以任何方式重新排序数组 $$$a$$$ 的所有元素。此类操作的执行时间为 $$$c$$$ 秒。
您需要将数组 $$$a$$$ 转换为数组 $$$b$$$。
Frisk 想尽快解决这个难题。帮助 Frisk 确定解决难题所需的最短时间。如果无解,则输出$$$-1$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$c$$$ ($$$1 \le n, c \le 100$$$) - 数组 $$$a$$$ 和 $$$b$$$ 的长度以及第二个操作的成本。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 100$$$) - 第一个数组的元素。
每个测试用例的第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le 100$$$) - 第二个数组的元素。
输出
对于每个测试用例,输出一个整数,表示解决难题所需的最小秒数,如果无法解决难题,则输出 $$$-1$$$。
示例
输入复制
63 55 2 32 3 43 31 2 34 5 64 44 5 2 33 5 1 26 42 4 5 3 6 85 8 3 1 2 55 115 8 11 14 1716 12 10 10 63 520 14 2012 18 17
输出复制
6-138-112
注意
在第一个测试用例中,仅使用减法不可能将 $$$a$$$ 转换为 $$$b$$$,因为 $$$a_2 \lt b_2$$$。让我们重新排列数组 $$$a$$$ 的元素,如下所示:$$$[5, 2, 3] \Rightarrow [2, 3, 5]$$$。现在,从 $$$a_3$$$ 中减一就足够了,我们得到数组 $$$a$$$ 在 $$$5 + 1 = 6$$$ 秒内等于数组 $$$b$$$。
在第二个测试用例中,$$$a$$$ 的所有元素都小于 $$$b$$$ 的所有元素,这意味着 $$$a$$$ 无法转换为 $$$b$$$。
在第三个测试用例中,您可以选择不重新排列元素并得到答案$$$3$$$。如果您至少重新排列一次,答案将至少为 $$$4$$$,因此最佳答案为 $$$3$$$ 秒。
在第六个测试用例中,数组可以重新排列如下:$$$[14, 20, 20]$$$。可以看出,成本将为 $$$5 + (14 - 12) + (20 - 18) + (20 - 17) = 12$$$。