最大化最大公约数

时间限制：2s
空间限制：1024MB

题目描述

给定一个长度为 $N$ 的正整数序列 $A=(A_1,A_2,\ldots,A_N)$。你至多可以执行 $K$ 次操作，每次选择一个下标 $i$，将 $A_i$ 增加 $1$。

求操作后整个序列的最大公约数可能达到的最大值。

输入格式

N K
A_1 A_2 ... A_N

输出格式

输出一个整数，表示可能得到的最大最大公约数。

样例输入 1

3 6
3 4 9

样例输出 1

5

样例输入 2

3 4
30 10 20

样例输出 2

10

样例输入 3

5 12345
1 2 3 4 5

样例输出 3

2472

数据范围

• $2\le N\le3\times10^5$；
• $1\le K\le10^{18}$；
• $1\le A_i\le3\times10^5$。