Louis L Le Roi-Univers 下令改善从皇宫看到的景观。陛下更喜欢看到一座高山。

首席景观经理打算为 Louis 建造一座山。他将景观表示为单位正方形网格上的平面图。其中一些正方形已经填满了岩石，而另一些则是空的。这极大地简化了设计。单位正方形足够小，从皇宫看去，景观显得很平滑。

首席景观经理有一份景观规划——即每一单位宽度上岩石填充列的高度。他打算在现有景观之上最多增加 $n$ 个单位的石块，以建造一座尽可能高的山峰。不幸的是，石堆非常不稳定。一个单位的石块只有在它正下方有另一个已填充的石块或岩石，且其左下方和右下方的正方形也已经被填充的情况下，才能放置。

现有景观 改进后的景观

你的任务是帮助首席景观经理确定他能建造的最高山峰的高度。

输入格式

输入文件的第一行包含两个整数 $w$ —— 现有景观的宽度，以及 $n$ —— 最多可以增加的石块数量 ($1 \le w \le 100\,000$, $0 \le n \le 10^{18}$)。

接下来的 $w$ 行，每行包含一个整数 $h_i$ —— 现有景观列的高度 ($1 \le h_i \le 10^9$)。

输出格式

输出文件应包含一个整数 —— 在以稳定方式增加最多 $n$ 个单位石块后，可能达到的最大景观高度。

样例

样例输入 1

8 4
3
4
2
1
3
3
2
4

样例输出 1

5

样例输入 2

3 100
3
3
3

样例输出 2

4