题目描述

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

输入格式

第一行有2个整数，表示方块数n(<=1000)和屏幕的宽度w(<=1000)，空格隔开。 第2行~i+1行，每行一个数，为方块的边长。

输出格式

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

样例 #1

样例输入 #1

3 5
2
1
3

样例输出 #1

4

提示

样例图示：