AT_abc136_e.[ABC136E] Max GCD

有一个长度为 $N$ 的整数序列 $A_1,\ A_2,\ \cdots,\ A_N$。

你可以进行如下操作 $0$ 次或多次，最多不超过 $K$ 次：

• 选择 $1$ 到 $N$ 之间的两个整数 $i,\ j$，且 $i \neq j$，将 $A_i$ 加 $1$，将 $A_j$ 减 $1$。操作后，序列中的某些元素可以变为负数。

请计算，经过操作后，作为能整除 $A$ 的所有元素的正整数中的最大值是多少。这里，正整数 $x$ 能整除整数 $y$，是指存在某个整数 $z$，使得 $y = xz$。

输入以如下格式从标准输入读入：

$N$ $K$ $A_1$ $A_2$ $\cdots$ $A_{N-1}$ $A_N$

输出经过操作后，能整除 $A$ 的所有元素的正整数中的最大值。

限制条件

• $2 \leq N \leq 500$
• $1 \leq A_i \leq 10^6$
• $0 \leq K \leq 10^9$
• 所有输入均为整数

样例解释 1

例如，可以通过如下操作使 $7$ 能整除 $A$ 的所有元素：

• 令 $i = 2, j = 1$，此时 $A$ 变为 $(7, 21)$。
  此外，无法使 $8$ 或更大的整数整除 $A$ 的所有元素。

样例解释 2

例如，可以进行如下 $5$ 次操作：

• 令 $i = 2, j = 1$，此时 $A$ 变为 $(2, 6)$。
• 令 $i = 2, j = 1$，此时 $A$ 变为 $(1, 7)$。
• 令 $i = 2, j = 1$，此时 $A$ 变为 $(0, 8)$。
• 令 $i = 2, j = 1$，此时 $A$ 变为 $(-1, 9)$。
• 令 $i = 1, j = 2$，此时 $A$ 变为 $(0, 8)$。
  此时，$0 = 8 \times 0,\ 8 = 8 \times 1$，因此 $8$ 能整除 $A$ 的所有元素。此外，无法使 $9$ 或更大的整数整除 $A$ 的所有元素。