题目描述

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

格式

输入格式

第 \(1\) 行有 \(2\) 个整数，表示方块数 \(n\) 和屏幕宽度 \(w\)，之间用 \(1\) 个空格分隔。
第 \(2 \sim i+1\) 行，每行 \(1\) 个整数，为第 \(i\) 个方块的边长 \(a\)。

输出格式

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

样例1

样例输入1

3 5
2
1
3

样例输出1

4

来源

地址：\(\text{Online~Judge}\)
作者：征宇
模拟赛\(T3\)