Mountain Construction Optimization

Louis L Le Roi-Univers has ordered an improvement of the landscape seen from his palace. His Majesty desires a high mountain. The Chief Landscape Manager represents the landscape as a grid of unit squares. Some squares are already filled with rock, while others are empty. He has a plan giving the initial heights of the rock‐filled columns. He is allowed to add at most n extra stone squares (each of unit area) on top of the existing landscape in order to build a mountain with as high a peak as possible.

However, piles of stones are unstable. A stone square can be placed only exactly on top of an already filled square (either rock or stone), and, in addition, the squares immediately to the bottom‐left and bottom‐right must be filled. In other words, if a stone is placed to achieve a final height X at some column j, then in order to place the stone at position j at level X (above the initial rock height H[j]), the positions at columns j−1 and j+1 must already be filled up to level X−1.

This rule forces the additional stones to form a pyramid shape. Formally, if you wish to achieve a mountain with peak height X at column j, then for every integer d with 1 ≤ d ≤ X−1 (and such that the columns exist), the final height at column j−d and at column j+d must be at least X−d. Note that if a column already has a rock height greater than or equal to X−d, no stone is needed there.

Your task is to determine the maximum possible peak height that can be achieved by adding at most n stone squares. The final mountain (i.e. the pyramid) must be completely contained within the landscape; hence if the peak is at column j and the mountain has peak height X, then we must have j ≥ X−1 and j ≤ m−X, so that all required neighbors exist.

Mathematically, for a candidate mountain with peak height X placed at column j, the extra stones required in the peak and its left wing are:

$$\max(0, X - H[j]) + \sum_{d=1}^{X-1} \max(0, (X-d) - H[j-d]), $$

and similarly for the right wing:

$$\sum_{d=1}^{X-1} \max(0, (X-d) - H[j+d]).$$

Your goal is to choose a peak position and a peak height X (subject to the boundary restrictions) so that the total number of stones required does not exceed n and X is maximized.

inputFormat

The first line contains two integers m and n, where m is the number of columns and n is the maximum number of stone squares that can be added. The second line contains m integers, where the i-th integer represents the initial height H[i] of column i (0-indexed).

outputFormat

Output a single integer representing the maximum possible peak height of the mountain that can be built.

sample

5 4
2 1 1 1 2

3