Сколько минут до партии

На заводе стоит линия из n станков. Станок номер *i* делает одну деталь ровно за a[i] минут и сразу начинает следующую (перерывов нет).

Начальник смены хочет понять, через сколько минут со старта на складе гарантированно будет готово k деталей (может быть больше).

Найди минимальное целое число минут.

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

Формат ввода

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

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

Выведи одно целое число — минимальное время (в минутах), через которое суммарно будет сделано хотя бы k деталей.

Ограничения

• 1 ≤ n ≤ 8000
• 1 ≤ k ≤ 10^9
• 1 ≤ ai ≤ 10^9

Пример

Ввод:

3 7
3 2 5

Вывод:

8

Ключевое наблюдение: если дать линии больше времени, деталей станет не меньше. Значит, условие «успеем сделать хотя бы k» монотонное по времени, и можно искать ответ бинарным поиском.

Как проверить время t? Станок с периодом a[i] за t минут сделает ровно t // a[i] деталей (первая деталь появляется через a[i] минут, затем каждые a[i]). Тогда всего: sum(t // a[i]).

Почему бинарный поиск работает: функция made(t) = sum(t // a[i]) не убывает, поэтому множество подходящих t — это «хвост» вида [T, +∞). Нам нужен самый первый T.

План:

• Прочитай n, k и массив a.
• Заведи функцию проверки can(t): посчитай total += t // a[i], и если total >= k, можно сразу вернуть True (ускоряет и избегает лишних больших сумм).
• Выбери границы:
• lo = 0 (за 0 минут сделано 0).
• hi = min(a) * k — этого точно хватит, потому что самый быстрый станок один сделает k деталей.
• Бинарный поиск по целым: пока lo < hi, возьми mid, проверь can(mid) и сдвинь границу к минимальному подходящему.
• Ответ — lo.

Сложность: O(n * log(hi)) ≈ O(n * log(min(a)*k)), при n до 8000 проходит легко.

Частая ошибка: использовать 32-битные типы/переполнить при min(a)*k или при сумме. Держи всё в 64-битных целых и делай ранний выход, как только набрали k.