题目描述

我们有一个由 $N$ 个整数组成的序列：$A_1, A_2, \cdots, A_N$。

你可以进行 $0$ 到 $K$ 次（包括 $K$）之间的以下操作：

• 选择两个整数 $i$ 和 $j$，使得 $i \neq j$，且 $i$ 和 $j$ 都在 $1$ 到 $N$ 之间（包括 $1$ 和 $N$）。将 $A_i$ 加 $1$，并将 $A_j$ 减 $1$，可能会产生负元素。

计算在进行操作后，可以整除 $A$ 的每个元素的最大正整数。这里一个正整数 $x$ 可以整除一个整数 $y$ 当且仅当存在一个整数 $z$ ，使得 $y = xz$。

约束条件

• $2 \leq N \leq 500$
• $1 \leq A_i \leq 10^6$
• $0 \leq K \leq 10^9$
• 输入中所有的值都是整数。

---

输入

从标准输入读入输入数据。

输入数据的格式如下：

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

---

输出

打印出在进行操作后，可以整除 $A$ 的每个元素的最大正整数。

---

示例输入 1

2 3
8 20

示例输出 1

7

如果我们执行以下操作，$7$ 将整除 $A$ 的每个元素：

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

我们无法得到使得大于等于 $8$ 的整数整除 $A$ 的每个元素的情况。

---

示例输入 2

2 10
3 5

示例输出 2

8

考虑执行以下五个操作：

• 选择 $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$ 的每个元素的情况。

---

示例输入 3

4 5
10 1 2 22

示例输出 3

7

---

示例输入 4

8 7
1 7 5 6 8 2 6 5

示例输出 4

5