题目描述

首先把经典的俄罗斯方块游戏简化一下：方块有顺序地从屏幕顶端掉下至底部，当碰到障碍物或底部时将停下，同时变成新的障碍物。​游戏规则规定，只能在方块下落停止前决定下落时的横向位置，使这个方块变成障碍物后的高度最低，且如果有几种横向位置使这个方块变成障碍物后的高度最低时，取最左边的横向位置下落​。下图为俄罗斯方块样例示意图。

输入格式

第 1 行有 2 个整数，表示方块数 n 和屏幕宽度 w，之间用 1 个空格分隔。

第 2 行 i+1 行，每行 1 个整数，为第 i 个方块的边长 a。

输出格式

输出一个整数，表示最后障碍物的最高点高度。

样例

3 5
2
1
3

4

解释#1

按照上面题目描述规定，最终按上图落下，因此高度为 4。

说明/提示

对于 100% 的数据满足：1≤w≤20,1≤a≤w,1≤n≤100。