问题描述

某工厂在一条装配线的末尾有一个装箱的机器人，恰有两个箱子打开着。机器人将物品一件接一件地装进任意一个打开的箱子内。箱子是完全相同的，一个箱子能在给定的重量范围内容纳多件物品。更确切地，机器人能完成以下四种命令：

• 1.将当前的物品装进箱子1。
• 2.将当前的物品装进箱子2。
• 3.将箱子1关上并打开一个新的空箱来代替这个关上的箱子。
• 4.将箱子2关上并打开一个新的空箱来代替这个关上的箱子。

一条装箱的命令只有在下述条件下被执行：当前物品的重量加上箱中已有物品的重量之和不超过限度范围。给出你一个物品重量的序列和对所有箱子适用的一个重量范围，编写一个程序计算出能将所有物品装进箱子，所需的箱子最少数目。

输入数据：binpack.in

输入文件由整形数据构成。输入文件的第一行包含重量限度L（1≦L≦100），这个范围对所有的箱子适用；第二行包含物品的数目N（1≦N≦5000）；以下的N行每行是一件物品的重量，每件重量在1至100之间。

输出数据：binpack.out

在第一行显示能装下所有物品所需箱子的最小数目。

输入输出示例：

8
6
4
2
5
3
5
4

3