配点 : $600$ 点

問題文

$N$ 項からなる正整数列 $A = (A_1, A_2, \ldots, A_N)$ が与えられます。あなたはこの数列に対して、次の操作を $0$ 回以上 $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)$ としてありうる最大値を出力してください。

3 6
3 4 9

5

例えば以下のようにして、$\gcd(A_1, A_2, A_3) = 5$ を実現できます。

• $i = 1$ に対して $2$ 回、$i = 2$ に対して $1$ 回、$i=3$ に対して $1$ 回の操作を行う。合計の操作回数は $4$ 回で、$K=6$ 以下である。
• 操作の結果、$A_1 = 5$, $A_2 = 5$, $A_3 = 10$ となり、$\gcd(A_1, A_2, A_3) = 5$ である。

3 4
30 10 20

10

操作を一度も行わないことで、$\gcd(A_1, A_2, A_3) = 10$ を実現できます。

5 12345
1 2 3 4 5

2472