Будівництво високого амбару#10554

Будівництво високого амбару

1 секунда

128 мегабайтів

Складна

Фермер Джон будує абсолютно новий $n$ -поверховий корівник за допомогою своїх $k$ корів. Щоб завершити будівництво якомога швидше, йому потрібна ваша допомога, щоб визначити, як розподілити роботу між коровами.

Кожна корова повинна бути призначена рівно на один з $n$ поверхів, і на кожному поверсі повинна працювати хоча б одна корова. Для завершення $i$ -го поверху потрібно $a_{i}$ a_i одиниць роботи. Оскільки кожна корова виконує одну одиницю роботи за годину, якщо на поверсі $i$ працюють $c$ корів, то цей поверх буде побудовано за $a_{i} / c$ a_i / c одиниць часу.

З міркувань безпеки будівництво на поверсі $i + 1$ i + 1 не може розпочатися до тих пір, поки не буде завершено будівництво поверху $i$ .

Визначте мінімальний загальний час, необхідний для завершення будівництва корівника, якщо корови оптимальним чином розподілені по поверхах. Виведіть відповідь, округлену до найближчого цілого числа. Гарантується, що точна відповідь відрізняється від будь-якого цілого числа більше ніж на $0.1$ .

Вхідні дані

У першому рядку містяться два цілих числа $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5) та $k (n \leq k \leq 1 0^{12})$ k~(n \le k \le 10^{12}).

У наступних $n$ рядках містяться значення $a_{1}, \dots, a_{n}$ a_1, \ldots, a_n, де кожне $a_{i}$ a_i є додатним цілим числом, що не перевищує $1 0^{12}$ 10^{12}.

Вихідні дані

Виведіть мінімальний час, необхідний для завершення будівництва корівника, округлений до найближчого цілого числа.

Приклади

Приклад 1