풍경 개선

루이 르 루아위니베르 국왕이 왕궁에서 보이는 풍경을 손보라고 명령했다. 국왕은 높은 산을 보고 싶어 한다.

수석 조경사가 국왕을 위해 산을 쌓기로 했다. 그는 풍경을 단위 정사각형 격자 위의 평면 그림으로 나타낸다. 어떤 칸은 이미 바위로 차 있고 나머지는 비어 있다. 이렇게 두면 설계가 훨씬 간단해진다. 단위 정사각형은 충분히 작아서 왕궁에서 보면 풍경이 매끄럽게 보인다.

수석 조경사에게는 풍경 설계도가 있다. 너비 방향으로 각 열마다 바위가 차 있는 높이를 적어 둔 것이다. 그는 기존 풍경 위에 돌을 최대 $n$칸까지 얹어 봉우리를 될 수 있는 대로 높게 만들려고 한다. 그런데 돌무더기는 잘 무너진다. 돌 한 칸은 돌이나 바위로 이미 채워진 칸의 바로 위에만 놓을 수 있고, 놓으려는 칸의 왼쪽 아래 칸과 오른쪽 아래 칸도 이미 채워져 있어야 한다. 주어진 너비 바깥에는 칸이 아예 없으므로 그 자리는 채워진 것으로 치지 않는다. 원래 있던 바위는 이 조건과 상관없이 그대로 남는다.

기존 풍경	개선한 풍경

수석 조경사가 만들 수 있는 봉우리의 최대 높이를 구하라.

첫째 줄에 기존 풍경의 너비 $w$와 새로 얹을 수 있는 돌의 최대 개수 $n$이 주어진다 ($1 \le w \le 100000$, $0 \le n \le 10^{18}$).

다음 $w$개 줄에 각 열의 기존 높이 $h_i$가 한 줄에 하나씩 주어진다 ($1 \le h_i \le 10^9$).

돌을 최대 $n$칸까지 무너지지 않게 쌓았을 때 나올 수 있는 풍경의 최대 높이를 정수 하나로 출력한다.