题目描述
首先把经典的俄罗斯方块游戏简化一下:方块有顺序地从屏幕顶端掉下至底部,当碰到障碍物或底部时将停下,同时变成新的障碍物。游戏规则规定,只能在方块下落停止前决定下落时的横向位置,使这个方块变成障碍物后的高度最低,且如果有几种横向位置使这个方块变成障碍物后的高度最低时,取最左边的横向位置下落。
输入格式
第1行有2个整数,表示方块数n和屏幕宽度w,之间用1个空格分隔。
第2行~i+1行,每行1个整数,为第i个方块的边长a。
输出格式
输出一个整数,表示最后障碍物的最高点高度。
样例数据
input
3 5
2
1
3
output
4
数据规模与约定
时间限制:$1 \text{s}$
空间限制:$128 \text{MB}$