← 返回题目列表

Codeforces · 354/C

C. Vasya 和美丽的阵列

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

Vasya 的生日即将到来,他的妈妈决定给他一个长度为 n 的正整数 a 数组。

Vasya 认为数组的美在于其所有元素的最大公约数。当然,他的妈妈想给他一个尽可能漂亮的阵列(尽可能美丽)。不幸的是,店里只剩下一排了。从好的方面来说,卖家说他可以减少数组中的一些数字(每个数字最多减少 k)。

如果满足以下条件,卖方可以从数组a中获取数组b:bi > 0; 对于所有 1 ≤ i ≤ n,0 ≤ ai - bi ≤ k。

帮助妈妈找到她送给 Vasya 的阵列的最大可能的美丽(卖家可以获得)。

输入

第一行包含两个整数 n 和 k (1 ≤ n ≤ 3·105; 1 ≤ k ≤ 106)。第二行包含 n 个整数 ai (1 ≤ ai ≤ 106) — 数组 a。

输出

在单行中打印一个数字——结果数组的最大可能的美感。

示例

输入 #1

6 1
3 6 10 12 13 16

输出 #1

3

输入 #2

5 3
8 21 52 15 77

输出 #2

7

注意

在第一个示例中我们可以获得数组:

3 6 9 12 12 15

在第二个示例中,我们可以获得下一个数组:

7 21 49 14 77