该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

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

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

选择其中一个数加一。

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

Format

Input

第一行两个正整数 $N（1<N\le3\times10^5）$ 和 $K（\le10^{18}）$。

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

Output

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

Samples

4 5
10 1 2 22

2

Limitation

1s, 1024KiB for each test case.