Минимальная скорость зачистки кристаллов

В игре «Башня кристаллов» у тебя есть n куч кристаллов. За один час герой выбирает ровно одну кучу и разбивает в ней до k кристаллов (если в куче меньше k, он добивает её полностью за этот час).

Нужно подобрать минимальную целую скорость k, чтобы гарантированно зачистить все кучи не позже чем за H часов.

Важно: H может быть очень большим (вплоть до 1e9), то есть значения могут не помещаться в 32-битный тип (как на олимпиадах). В Python это не проблема.

Формат ввода

Первая строка: два целых числа n и H. Вторая строка: n целых чисел a1, a2, ..., an — размеры куч.

Формат вывода

Одно целое число — минимальная подходящая скорость k.

Ограничения

• 1 ≤ n ≤ 5000
• n ≤ H ≤ 10^9 (гарантируется, что H ≥ n)
• 1 ≤ ai ≤ 10^6

Пример

Ввод:

4 8
3 6 7 11

Вывод:

4

Пояснение: при k = 4 нужно 1 + 2 + 2 + 3 = 8 часов, а при k = 3 уже 1 + 2 + 3 + 4 = 10 — не успеваем.

Ключевое наблюдение: если выбрать скорость k, то для каждой кучи размера a нужно ровно ceil(a / k) часов (за час можно бить только одну кучу). Значит, всего часов будет S(k) = сумма ceil(ai / k). Чем больше k, тем меньше или равно S(k). Это монотонность и даёт «бинарный поиск по ответу».

Почему работает: функция «успеваем ли за H часов» меняется только в одну сторону. Для маленьких k не успеваем (часов много), начиная с некоторого порога начинаем успевать, и дальше всегда успеваем.

План:

• Задай границы поиска: k не меньше 1 и не больше max(ai) (быстрее максимальной кучи не нужно).
• Напиши проверку ok(k): посчитать total = sum(ceil(ai/k)) и сравнить total <= H.
• Удобная формула без вещественных: ceil(a/k) = (a + k - 1) // k.
• Дальше обычный бинарный поиск по целым:
• mid = (lo + hi) // 2.
• Если ok(mid) истинно, сдвигай правую границу (hi = mid), иначе левую (lo = mid + 1).
• Ответ будет lo.

Сложность: проверка работает за O(n), бинарный поиск делает O(log max(ai)) шагов, итого O(n log maxA) — при n = 5000 быстро.

Частая ошибка: считать ceil(ai/k) через обычное деление и округление — можно получить погрешности и ошибки на больших числах. Используй только целочисленную формулу (a + k - 1) // k.