eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Улучшение ландшафта

Улучшение ландшафта

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Луис ЛеРуа Универс приказал улучшить ландшафт, который видно из королевского дворца. Его Величество предпочитает смотреть на высокую гору.

Главный менеджер по ландшафту собирается увеличить высоту горы для Луи. Пейзаж представлен в виде плоского изображения на сетке единичных квадратов. Некоторые квадраты уже заполнены камнем, в то время как другие являются пустыми. Это значительно упрощает конструкцию. Единичные квадраты достаточно малы, а пейзаж кажется гладким из королевского дворца.

Главный Пейзажный менеджер имеет план ландшафта - высоты всех заполненных камнем столбцов по всей ширине. Он собирается добавить не более n квадратных плиток камня на верх существующего ландшафта так чтобы высота ландшафта была наибольшей. К сожалению, груды камней весьма неустойчивы. Квадратный каменный блок можно разместить только над другим камнем, причем квадраты снизу слева и снизу справа от него должны быть также заполнены.

prb7572.gif

Вам следует помочь Главному Пейзажному менеджеру определить наибольшую высоту горы, которую он сможет построить.

Вхідні дані

Первая строка содержит два числа: w - ширина существующего ландшафта и n - наибольшее количество квадратных камней, которое можно добавить (1w10^5, 0n10^18).

Каждая из следующих w строк содержит одно число h[i] (1h[i]10^9) - начальную высоту колонки ландшафта.

Вихідні дані

Вывести наибольшую возможную высоту ландшафта после добавления не более n единичных квадратных камней при условии стабильности всей конструкции.

Приклад

Вхідні дані #1
8 4
3
4
2
1
3
3
2
4
Вихідні дані #1
5
Вхідні дані #2
3 100
3
3
3
Вихідні дані #2
4
Джерело 2015 ACM NEERC, Semifinals, December 6, Problem L