题目描述

给定一个由 $N$ 个正整数组成的序列：$A = (A_1, A_2, \ldots, A_N)$。你可以对这个序列执行以下操作，至少为零次、最多为 $K$ 次：

• 选择 $i\in \{1,2,\ldots,N\}$ 并将 $A_i$ 增加 $1$。

在执行完操作后，找出 $\\gcd(A_1, A_2, \ldots, A_N)$ 的最大可能值。

约束条件

• $2\leq N\leq 3\times 10^5$
• $1\leq K\leq 10^{18}$
• $1 \leq A_i\leq 3\times 10^5$

输入

从标准输入中按以下格式获得输入：

$N$ $K$ $A_1$ $A_2$ $\ldots$ $A_N$

输出

打印执行操作后 $\\gcd(A_1, A_2, \ldots, A_N)$ 的最大可能值。

示例输入 1

3 6
3 4 9

示例输出 1

5

一种使得 $\\gcd(A_1, A_2, A_3) = 5$ 的方法如下：

• 对 $i = 1$ 执行两次操作，对 $i = 2$ 执行一次操作，对 $i = 3$ 执行一次操作，总共四次操作，不超过 $K=6$。
• 现在我们有 $A_1 = 5$，$A_2 = 5$，$A_3 = 10$，它们的 $\\gcd(A_1, A_2, A_3) = 5$。

示例输入 2

3 4
30 10 20

示例输出 2

10

不执行任何操作即可使得 $\\gcd(A_1, A_2, A_3) = 10$。

示例输入 3

5 12345
1 2 3 4 5

示例输出 3

2472