题目描述

有一座残破的石质假山，可以把它看作二维平面上用单位宽度的岩石堆叠而成的。经过风雨的侵蚀，它已经没有以往那么雄伟了，现在需要你的帮助来让它变得更高一些。

由于经费有限，最多只能提供给你$\red{n}$块石块，希望你能够把它们堆到假山上之后得到的山峰最高（也就是二维平面上最高的一列的高度最高）。但是新堆叠上去的石块需要符合一定的稳定结构，每一块新增的石块只能放在一个已有岩石或者已填充的石块的正上方，并且该石块的左下方和右下方也必须都有一个岩石或者石块。能否请你计算得出能够修复出来的假山的高度最高可以是多少？

如上图所使，当残破的假山如左边所示，在最多提供$\red{n}$个石块时，能够修复出来的最高的假山为右图。

输入格式

第一行输入两个正整数$\red{w,n}$分别表示现存假山的宽度和最多提供的石块的个数；

接下来$\red{w}$行，每行一个正整数$\red{h_i}$表示现存假山的每一列的高度。

输出格式

输出一个整数表示修复后的假山的最高高度

样例

输入样例

3 100
2
2
2

输出样例

3

提示

对于其中$\red{20\%}$的数据$\red{1<=w<=10,0<=n<=10,1<=h_i<=10}$

另有$\red{50\%}$的数据$\red{1<=w<=1000,0<=n<=10^9,1<=h_i<=10^9}$；

对于$\red{100\%}$的数据$\red{1<=w<=100000,0<=n<=10^{18},1<=h_i<=10^9}$。