Фермер Джон строит новый \(N\)-этажный амбар с помощью своих \(K\) коров
(\(1 \leq N \leq K \leq 10^{12}\) и \(N \leq 10^5\)).
Чтобы сделать работу быстрее ему нужно оптимально распределить работу
между коровами.
Каждая корова должна быть назначена на работу ровно на один этаж.
И на каждый этаж должна быть назначена хотя бы одна корова.
\(i\)-ый этаж требует выполнения \(a_i\) единиц работы , каждая корова завершает одну единицу
работы ровно за час. Поэтому если \(c\) коров работают на этаже \(i\), то они выполнят всю
работу ровно за \(a_i / c\) единиц времени. Из соображений безопасности, этаж \(i\)
должен быть завершён прежде чем начнётся работа на этаже \(i+1\).
Вычислите минимальное количество времени, за которое может быть построен амбар,
если коровы будут распределены по этажам оптимальным способом. Выведите это число
округлённым к ближайшему целому. Гарантируется, что решение будет более чем на 0.1
от границы между двумя целыми числами.
ФОРМАТ ВВОДА (файл tallbarn.in):
Первая строка ввода содержит
\(N\) и
\(K\).
Следующие \(N\) строк содержат \(a_1 \ldots a_N\), каждое - положительное целое не более
чем \(10^{12}\).
ФОРМАТ ВЫВОДА (файл tallbarn.out):
Выведите минимальное время, требуемое чтобы построить амбар, округлённое
до ближайшего целого.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 5
10
4
|
5
|