3988: 新俄罗斯方块

内存限制：512 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：1 解决：1

题目描述

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

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

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

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

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

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

输入

第一行输入两个整数 � 和 �。

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

输出

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

样例输入 复制 

3 6
2
1
4

样例输出 复制 

5

提示

样例

输入
复制 

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 解释

如下图所示。

第 1 个方块大小为 2×2，用 * 表示。

第 2 个方块大小为 1×1，用 @ 表示。

第 3 个方块大小为 4×4，用 # 表示。

两侧的 | 字符表示屏幕的边界，屏幕宽度为 6。 

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

数据范围

对于 100% 的数据，满足 1≤�≤100，1≤�≤20，1≤��≤�。

来源/分类

提交提交记录统计露一手!