Максимальний НСД

Дано $n$ цілих чисел $a_1,a_2,\dots ,a_n$.

За одну операцію ви можете вибрати два індекси $i$ та $j$ такі, що $i\ne j$. Після чого збільшити $a_i$ на $1$, а $a_j$ зменшити на $1$ (навіть якщо вийде від'ємне число).

Ви можете виконати цю операцію не більше $k$ разів (або не виконувати взагалі). Знайдіть максимально можливе число, яке ділитиме усі числа, після виконання операцій. Ціле додатне число $x$ ділить ціле число $y$, якщо існує таке ціле число $z$, що $y=xz$.

Giriş verilənləri

Перший рядок містить два цілі числа $n$ та $k$ ($2\le n\le 500$, $0\le k\le 10^9$).

Другий рядок містить $n$ цілих чисел $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 10^6$).

Çıxış verilənləri

Виведіть одне ціле число — відповідь на задачу.

Nümunələr