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

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

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

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

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

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

Каждая из следующих w строк содержит одно число hi (1 ≤ hi ≤ 109) - начальную высоту колонки ландшафта.

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

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