题目描述

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

输入格式

第一行仅包含两个正整数，分别表示方块数n和屏幕宽度w，两数间用一个空格分隔。

接下来的n行，每行仅有一个正整数，表示各个方块的边长a。

输出格式

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

样例

输入

3 5
2
1
3

输出

4

提示

数据范围：1<=w<=20，1<=a<=w，1<=n<=100.