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