Landscape Improved

King Louis L Le Roi-Univers has ordered his staff to improve the view from the royal palace. His Majesty wants to see a high mountain.

The Chief Landscape Manager is going to raise a mountain for the king. He draws the landscape as a flat picture on a grid of unit squares. Some squares are already filled with rock and the rest are empty. That simplifies the design a great deal. Unit squares are small enough that the landscape still looks smooth from the palace.

The Chief Landscape Manager has a plan of the landscape: the height of the rock in every column of the grid. He wants to put at most $n$ unit squares of stone on top of the existing landscape so that the peak is as high as possible. Piles of stone are unstable. A unit square of stone may be placed only directly on top of a square that is already filled with stone or rock, and the squares immediately to its bottom left and bottom right must be filled as well. No squares exist outside the given width, so those positions never count as filled. Rock that is already there is not affected by this condition and stays where it is.

Existing landscape	Improved landscape

Find the maximum height of the highest mountain the Chief Landscape Manager can build.

The first line contains two integers $w$, the width of the existing landscape, and $n$, the maximum number of stone squares to add ($1 \le w \le 100000$, $0 \le n \le 10^{18}$).

Each of the next $w$ lines contains one integer $h_i$, the height of one column of the existing landscape ($1 \le h_i \le 10^9$).

Print one integer: the maximum landscape height after at most $n$ unit squares of stone have been added in a stable way.