最大公约数

题目描述

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

你可以执行以下操作 $0$ 次以上 $K$ 次以下：

• 选择满足 $i \neq j$ 的 $1$ 到 $N$ 之间的两个整数 $i, 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 3
8 20

7

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

• 令 $i = 2, j = 1$。$A$ 变为 $(7, 21)$。

此外，无法让 $8$ 以上的整数整除 $A$ 的所有元素。

2 10
3 5

8

例如，按如下方式执行 $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$ 的所有元素。

4 5
10 1 2 22

7

8 7
1 7 5 6 8 2 6 5

5

数据范围

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