← 返回题目列表

Codeforces · 793/A

A. 奥列格和股份

中文机器翻译题面 查看原题

银行客户 Oleg 每天都会检查股价。他对 n 种股票价格感兴趣。今天,他观察到这些价格中的每一秒恰好有一个价格下跌 k 卢布(请注意,每一秒恰好有一个价格发生变化,但在不同的秒,不同的价格可能会发生变化)。价格可能会变成负值。奥列格觉得这个过程很有趣,他问金融分析师伊戈尔,所有n个价格变得相等所需的最短时间是多少,或者根本不可能?伊戈尔现在很忙,所以他请你帮助奥列格。你能回答这个问题吗?

输入

第一行包含两个整数 n 和 k (1 ≤ n ≤ 105, 1 ≤ k ≤ 109) - 股票价格的数量,以及某些价格每秒减少的卢布数量。

第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 109) - 初始价格。

输出

打印唯一包含价格变得相等所需的最小秒数的行,如果不可能,则打印“-1”。

示例

输入 #1

3 3
12 9 15

输出 #1

3

输入 #2

2 2
10 9

输出 #2

-1

输入 #3

4 1
1 1000000000 1000000000 1000000000

输出 #3

2999999997

注意

考虑第一个例子。

假设第三个价格在第一秒内下降并等于 12 卢布,然后第一个价格下降并等于 9 卢布,在第三秒第三个价格再次下降并等于 9 卢布。在这种情况下,所有价格在 3 秒内变为 9 卢布。

可能还有其他可能性,但这会最大限度地缩短所有价格变得相等所需的时间。因此答案是3。

在第二个示例中,我们可以注意到第一和第二价格的平价不同,并且在所描述的过程中永远不会改变。因此,价格永远不可能变得平等。

在第三个示例中,可能会发生以下情况:首先,第二个价格下降,然后第三个价格下降,然后第四个价格下降。这种情况发生了 999999999 次,并且由于一秒钟内只能有一个价格下跌,因此整个过程需要 999999999 * 3 = 2999999997 秒。我们可以注意到这是最短的可能时间。