题目描述

众所周知，强哥有很多IKUN玩偶，它们喜欢玩叠叠乐！

今天强哥决定用IKUN玩偶们决定搞一件大事！他要尝试打破叠叠乐的吉尼斯世界纪录！

这里我们认为IKUN玩偶们的长宽高都是 $1$，没错IKUN玩偶是一个正方形

强哥找了一个宽度为 $n$ 的铁箱，现在强哥已经把一部分IKUN玩偶堆了进去。

现在在这个铁箱中，强哥已经摆了 $n$ 列IKUN玩偶，每列放了 $len_i$ 个玩偶

但是强哥发现如果要继续堆IKUN玩偶，IKUN玩偶们很容易倒！

所以接下去的IKUN玩偶摆放时，必须要保证左下，正下，右下三个位置都有IKUN玩偶，才能成功把这个IKUN玩偶放上去

假设需要在第 $i$ 列放下第 $j$ 个IKUN玩偶，则需要保证 $i-1,i,i+1$ 这三列都至少有 $j-1$ 个IKUN玩偶（所以第一列和最后一列已经无法再放IKUN玩偶了）

强哥现在还有 $m$ 个IKUN玩偶，请问他最高能把IKUN玩偶搭到多高？

输入格式(c.in)

从c.in文件里面输入

第一行包含两个整数 $n,m$，含义如题

接下来一行包含 $n$ 个整数 $len_i$ 表示每列IKUN玩偶的高度

输出格式 (c.out)

输出到c.out文件里面

输出一个整数表示最高能搭到的高度

8 4
3 4 2 1 3 3 2 4

5

一开始的情况：

放的操作如下：

可以在第 $7$ 列放两个IKUN玩偶，变成 3 4 2 1 3 3 4 4

再在第 $6$ 列放一个IKUN玩偶，变成 3 4 2 1 3 4 4 4

最后再第 $7$ 列放一个IKUN玩偶，变成 3 4 2 1 3 4 5 4

补充完4个玩偶后：

提示

对于 $30\%$ 的数据，满足 $n \leq 10，m \leq 1000$

对于 $50\%$ 的数据，满足 $n \leq 100，m \leq 1000000$

对于 $100\%$ 的数据，满足 $n \leq 1000，len_i \leq 100000，m \leq 10000000$