Problems
Максимальний НСД
Максимальний НСД
Дано $n$ цілих чисел $a_1, a_2, \dots, a_n$.
За одну операцію ви можете вибрати два індекси $i$ та $j$ такі, що $i \neq j$. Після чого збільшити $a_i$ на $1$, а $a_j$ зменшити на $1$ (навіть якщо вийде від'ємне число).
Ви можете виконати цю операцію не більше $k$ разів (або не виконувати взагалі). Знайдіть максимально можливе число, яке ділитиме усі числа, після виконання операцій. Ціле додатне число $x$ ділить ціле число $y$, якщо існує таке ціле число $z$, що $y=xz$.
\InputFile
Перший рядок містить два цілі числа $n$ та $k$ ($2 \leq n \leq 500$, $0 \leq k \leq 10^9$).
Другий рядок містить $n$ цілих чисел $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq 10^6$).
\OutputFile
Виведіть одне ціле число~--- відповідь на задачу.
Input example #1
2 3 8 20
Output example #1
7
Input example #2
2 10 3 5
Output example #2
8
Input example #3
4 5 10 1 2 22
Output example #3
7
Input example #4
8 7 1 7 5 6 8 2 6 5
Output example #4
5