题目描述

众所周知，徐老师很喜欢羊腿，甚至开了一家羊腿小店！

今天徐老师决定搞一件大事！他要尝试用羊腿打破搭积木的吉尼斯世界纪录！

这里我们认为徐老师用来搭的羊腿长宽高都是 $1$

徐老师找了一个宽度为 $n$ 的铁箱，现在徐老师已经把一部分羊腿堆了进去。

现在在这个铁箱中，徐老师已经摆了 $n$ 列羊腿，每列放了 $len_i$ 个羊腿

但是徐老师发现如果要继续堆羊腿，羊腿很容易倒！

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

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

徐老师现在还有 $m$ 个羊腿，请问他最高能把羊腿搭到多高？

输入格式

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

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

输出格式

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

数据范围

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

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

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

对于 $80\%$ 的数据，满足 $n \leq 10000，m \leq 100000000$

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

输入样例

8 4
3 4 2 1 3 3 2 4

输出样例

5

样例解释

可以在第 $7$ 列放两个羊腿，变成 3 4 2 1 3 3 4 4

再在第 $6$ 列放一个羊腿，变成 3 4 2 1 3 4 4 4

最后再第 $7$ 列放一个羊腿，变成 3 4 2 1 3 4 5 4