题目描述

小A是一个游戏开发工程师，他开发了一款新俄罗斯方块的游戏。

和传统的俄罗斯方块不同。这款新俄罗斯方块游戏，从屏幕顶部掉落的，只有各种大小的正方形方块，不会有其他形状。

在方块碰到屏幕底部或者碰到其他方块之前，玩家可以通过左移、右移方块选择方块的掉落位置，无论怎样移动，方块都不可能移出屏幕的宽度之外。

方块掉落到屏幕底部或者碰到其他方块时，会固定在当前的位置上。无论怎样堆叠，方块也不会消失。游戏的目标是使得方块堆叠的总高度最低，总高度越低、分数越高。

小A邀请好朋友小明来玩这个游戏。小明没有任何经验，玩家也无法预先看到接下来会有哪些大小的方块掉落。于是他选择了一个非常简单的策略：每当有一个方块落下时，他会看一下这个方块放到哪个位置会使得当前 堆叠的总高度最低，如果有多个位置满足要求，他会选择最左侧的位置 。

现已知屏幕宽度为W，在某轮游戏中，游戏从开始到结束，一共有N个方块落下，第i个正方形方块的边长为Ai。请编程计算出，按照小明的策略，方块堆叠的最低总高度是多少？

输入格式

第一行输入两个整数N和W。

接下来的N行，每行输入一个整数，表示每个方块的边长，方块将严格按照读入的顺序依次落下，在第i个方块固定之后，第i + 1个方块才会落下来。

输出格式

输出一个整数，按照小明的策略，游戏结束后方块的最低总高度是多少。

样例输入 1

3 6
2
1
4

样例输出 1

5

样例输入 2

7 7
2
3
1
2
3
2
3

样例输出 2

8

样例输入 3

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

样例输出 3

86

说明

样例 1 解释

如下图所示。 第1个方块大小为2×2，用*表示。 第2个方块大小为1×1，用@表示。 第3个方块大小为4×4，用#表示。 两侧的|字符表示屏幕的边界，屏幕宽度为6。

|  ####|
|  ####|
|  ####|
|**####| 
|**@   |

数据范围

对于100%的数据，满足1 ≤ N ≤ 100，1 ≤ W ≤ 20，1 ≤ Ai ≤ W。