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