H. Параллельная проверка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Соревнование завершилось — и теперь Артёму остаётся только проверить посылки команд на плагиат.

Всего у Артёма имеется $$$n$$$ посылок, проверка $$$i$$$-й посылки займёт $$$A_i$$$ квантов времени.

Проблема в том, что проверка не может длиться слишком долго — она должна быть завершена не более чем за $$$T$$$ квантов времени.

Для ускорения процесса Артём может его распараллелить, выделив $$$d$$$ потоков. В таком случае $$$i$$$-я посылка будет проверена за $$$\lceil\frac{A_i}{d}\rceil$$$ квантов времени (результат целочисленного деления, округлённый вверх).

Помогите Артёму найти минимальное количество потоков $$$d$$$ такое, что $$$\sum{\lceil\frac{A_i}{d}\rceil} \le T$$$.

Входные данные

В первой строке через пробел даны два целых числа $$$n$$$ и $$$T$$$ $$$(1 \le n \le 2 \cdot 10^5; n \le T \le 10^{12})$$$ — количество имеющихся посылок.

Во второй строке через пробел даны $$$n$$$ целых чисел $$$A_i$$$ $$$(1 \le A_i \le 10^{12})$$$ — количество квантов времени, занимаемое проверкой $$$i$$$-й посылки.

Выходные данные

В единственной строке выведите целое число $$$d$$$ $$$(1 \le d \le 10^{12})$$$ — минимальное количество потоков такое, что $$$\sum{\lceil\frac{A_i}{d}\rceil} \le T$$$.

Пример
Входные данные
5 22
15 130 120 78 43
Выходные данные
20
Примечание

Первый тестовый пример

При $$$d = 20$$$ решения проверяются за:

  • $$$\lceil\frac{15}{20}\rceil = 1$$$;
  • $$$\lceil\frac{130}{20}\rceil = 7$$$;
  • $$$\lceil\frac{120}{20}\rceil = 6$$$;
  • $$$\lceil\frac{78}{20}\rceil = 4$$$;
  • $$$\lceil\frac{43}{20}\rceil = 3$$$.

Суммарно при $$$d = 20$$$ используется $$$1 + 7 + 6 + 4 + 3 = 21$$$ квант времени.

При $$$d = 19$$$ решения проверяются за:

  • $$$\lceil\frac{15}{19}\rceil = 1$$$;
  • $$$\lceil\frac{130}{19}\rceil = 7$$$;
  • $$$\lceil\frac{120}{19}\rceil = 7$$$;
  • $$$\lceil\frac{78}{19}\rceil = 5$$$;
  • $$$\lceil\frac{43}{19}\rceil = 3$$$.

Суммарно при $$$d = 19$$$ используется $$$1 + 7 + 7 + 5 + 3 = 23$$$ квант времени.

Аналогично можно показать, что для всех $$$1 \le d \lt 19$$$ количество квантов времени так же не меньше $$$23$$$.

Отсюда следует, что при $$$T = 22$$$ значение $$$d = 20$$$ является минимально возможным.