← 返回题目列表

Codeforces · 2238/A

A. 纸莎草纸的另一个谜题

中文机器翻译题面 查看原题
你充满了决心。
— 传说之下

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

示例

输入
复制

6
3 5
5 2 3
2 3 4
3 3
1 2 3
4 5 6
4 4
4 5 2 3
3 5 1 2
6 4
2 4 5 3 6 8
5 8 3 1 2 5
5 11
5 8 11 14 17
16 12 10 10 6
3 5
20 14 20
12 18 17

输出
复制

6
-1
3
8
-1
12

注意

在第一个测试用例中,仅使用减法不可能将 $$$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$$$。