题目描述

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

输入格式

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

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

输出格式

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

样例数据

input

3 5 
2 
1
3

output

4

数据规模与约定

时间限制：$1 \text {s}$

空间限制：$64 \text {MB}$