Дано n цілих чисел a1,a2,…,an.
За одну операцію ви можете вибрати два індекси i та j такі, що i=j. Після чого збільшити ai на 1, а aj зменшити на 1 (навіть якщо вийде від'ємне число).
Ви можете виконати цю операцію не більше k разів (або не виконувати взагалі). Знайдіть максимально можливе число, яке ділитиме усі числа, після виконання операцій. Ціле додатне число x ділить ціле число y, якщо існує таке ціле число z, що y=xz.
Перший рядок містить два цілі числа n та k (2≤n≤500, 0≤k≤109).
Другий рядок містить n цілих чисел a1,a2,…,an (1≤ai≤106).
Виведіть одне ціле число — відповідь на задачу.