题目描述

有一个宽度为 $W$ 的游戏区域，底部被分成 $W$ 个单位宽度的位置。依次有 $N$ 个正方形方块竖直落下，第 $i$ 个方块的边长为 $A_i$。

放置一个边长为 $A_i$ 的方块时，可以选择任意一段连续的 $A_i$ 个位置。方块会落到这段位置当前最高高度处，放置后，这 $A_i$ 个位置的高度都变为原最高高度加 $A_i$。

每次放置时，应选择使放置后整体最高高度最小的位置；如果有多个位置符合要求，选择最左边的位置。请计算所有方块放置完毕后的整体最高高度。

输入格式

第一行包含两个整数 $N,W$，分别表示方块数量和游戏区域宽度。

接下来 $N$ 行，第 $i$ 行包含一个整数 $A_i$，表示第 $i$ 个方块的边长。

输出格式

输出一个整数，表示最终的整体最高高度。

3 6
2
1
4

5

7 7
2
3
1
2
3
2
3

8

12 20
8
15
18
12
3
4
2
12
7
7
15
6

86

数据范围与提示

• $1 \le N \le 100$
• $1 \le W \le 20$
• $1 \le A_i \le W$