В далёкой волшебной долине растёт древнее Древо Жизни, питаемое волшебными цветами. Каждому цветку нужно ровно $$$t_i$$$ дней, чтобы впитать магическую силу земли и полностью расцвести. Причём $$$i$$$-й цветок начинает расти только после того, как предыдущий закончил расти. Ожидать тяжело, поэтому...
У вас есть $$$M$$$ порций особого ускоряющего удобрения «Быстророст», каждая из которых:
Ваша задача — посчитать, какое минимальное суммарное время ожидания можно достичь, используя удобрения.
Первая строка содержит два целых числа $$$n$$$ и $$$M$$$ ($$$1 \leq n \leq 10^5$$$, $$$0 \leq M \leq 10^9$$$) — количество цветов и число доступных порций удобрения.
Вторая строка содержит $$$n$$$ положительных целых чисел $$$t_1, t_2, ..., t_n$$$ — сколько дней без удобрения требуется каждому цветку, чтобы зацвести. $$$(1 \le t_i \le 10^9)$$$
Одно число — минимальное количество дней, через которое при оптимальном распределении удобрений все цветы закончат расти и предстанут в полном цветении.
Тесты в этой задаче разбиты на 4 группы. Баллы за группу начисляются при прохождении всех тестов этой и всех необходимых групп. Примеры из условия не оцениваются.
| Подзадача | Баллы | Доп. ограничения | Необх. подзадачи |
| 1 | 10 | $$$M = 0$$$ | — |
| 2 | 13 | $$$M = 1$$$ | 1 |
| 3 | 42 | $$$M \leq 10^5$$$ | 1, 2 |
| 4 | 35 | — | 1-3 |
5 3 8 4 5 3 10
18
1 10 10
0
