Background

Special for beginners, ^_^

Description

给定一个长度为 $N$ 的整数序列：$A_1, A_2, \ldots, A_n$。

您可以执行以下操作 $0 \sim K$ 次：

选择两个整数 $i$ 和 $j$，满足 $i \ne j$ 并且 $1 \le i, j \le N$。令 $A_i$ 加上 $1$，令 $A_j$ 减去 $1$，可能产生负的元素。

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

Format

Input

第一行两个非负整数 $N（1<N\le500）$ 和 $K（\le10^9）$。

第二行给出 $N$个不会超过 $3\times10^6$ 的正整数 $A_i$ 。

Output

输出调整不超过 $K$ 次的情况下，能获得的序列的最大的最大公约数。

Samples

4 5
10 1 2 22

7

Limitation

1s, 1024KiB for each test case.