Улучшение ландшафта
Луис ЛеРуа Универс приказал улучшить ландшафт, который видно из королевского дворца. Его Величество предпочитает смотреть на высокую гору.
Главный менеджер по ландшафту собирается увеличить высоту горы для Луи. Пейзаж представлен в виде плоского изображения на сетке единичных квадратов. Некоторые квадраты уже заполнены камнем, в то время как другие являются пустыми. Это значительно упрощает конструкцию. Единичные квадраты достаточно малы, а пейзаж кажется гладким из королевского дворца.
Главный Пейзажный менеджер имеет план ландшафта - высоты всех заполненных камнем столбцов по всей ширине. Он собирается добавить не более n квадратных плиток камня на верх существующего ландшафта так чтобы высота ландшафта была наибольшей. К сожалению, груды камней весьма неустойчивы. Квадратный каменный блок можно разместить только над другим камнем, причем квадраты снизу слева и снизу справа от него должны быть также заполнены.
Вам следует помочь Главному Пейзажному менеджеру определить наибольшую высоту горы, которую он сможет построить.
Входные данные
Первая строка содержит два числа: w - ширина существующего ландшафта и n - наибольшее количество квадратных камней, которое можно добавить (1 ≤ w ≤ 10^5, 0 ≤ n ≤ 10^18).
Каждая из следующих w строк содержит одно число h[i] (1 ≤ h[i] ≤ 10^9) - начальную высоту колонки ландшафта.
Выходные данные
Вывести наибольшую возможную высоту ландшафта после добавления не более n единичных квадратных камней при условии стабильности всей конструкции.