Будівництво високого амбару
Фермер Джон будує новий n-поверховий амбар за допомогою своїх k корів. Щоб прискорити процес, йому потрібно оптимально розподілити роботу між коровами.
Кожна корова повинна бути закріплена за роботою на одному поверсі. На кожному поверсі має працювати принаймні одна корова. i-ий поверх вимагає виконання a[i] одиниць роботи, причому кожна корова виконує одну одиницю роботи за годину. Отже, якщо на поверсі i працюють c корів, вони завершать всю роботу за a[i] / c годин. З міркувань безпеки, робота на поверсі i повинна бути завершена до початку робіт на поверсі i + 1.
Обчисліть мінімальний час, за який може бути побудований амбар, якщо корови будуть розподілені по поверхах оптимально. Виведіть це число, округлене до найближчого цілого. Гарантується, що рішення буде більш ніж на 0.1 від межі між двома цілими числами.
Вхідні дані
Перша строка містить числа n (1 ≤ n ≤ 10^5) і k (n ≤ k ≤ 10^12). Наступні n строк містять a[1] .. a[n], кожне - додатне ціле число, не більше ніж 10^12.
Вихідні дані
Виведіть мінімальний час, потрібний для побудови амбару, округлений до найближчого цілого.