C. Уральские цветы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В далёкой волшебной долине растёт древнее Древо Жизни, питаемое волшебными цветами. Каждому цветку нужно ровно $$$t_i$$$ дней, чтобы впитать магическую силу земли и полностью расцвести. Причём $$$i$$$-й цветок начинает расти только после того, как предыдущий закончил расти. Ожидать тяжело, поэтому...

У вас есть $$$M$$$ порций особого ускоряющего удобрения «Быстророст», каждая из которых:

  • Мгновенно ускоряет рост одного цветка, и с этого момента он растёт вдвое быстрее (то есть оставшееся до цветения время делится нацело на 2).
  • Расходуется полностью после первого использования.

Ваша задача — посчитать, какое минимальное суммарное время ожидания можно достичь, используя удобрения.

Входные данные

Первая строка содержит два целых числа $$$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 группы. Баллы за группу начисляются при прохождении всех тестов этой и всех необходимых групп. Примеры из условия не оцениваются.

ПодзадачаБаллыДоп. ограниченияНеобх. подзадачи
110$$$M = 0$$$—
213$$$M = 1$$$1
342$$$M \leq 10^5$$$1, 2
435—1-3
Примеры
Входные данные
5 3
8 4 5 3 10
Выходные данные
18
Входные данные
1 10
10
Выходные данные
0