2210. Canoes

单点时限: 2.0 sec

内存限制: 256 MB

We are organizing a canoe tour. Canoes can be hired at the harbour. Canoes are all alike. A canoe can take at most two persons. The sum of weights of these persons cannot exceed the fixed maximal weight. We want to pay as little as possible so we should try to place all participants of our tour in the minimal number of canoes.

Write a program that:

  • reads the maximal weight of a canoe crew, the number of participants of the tour and the weight of each of them,

  • computes the minimal number of canoes that should be hired to place all the participants of the tour according to the rules,

  • writes the result.

输入格式

In the first line there is one integer w, 80<=w<=200, which is the maximal weight of a canoe crew.

In the second line there is one integer n, 1 <= n <= 30000, which is the number of participants of the tour.

Each of the following n lines contains one integer from the range [5..w]. These numbers equal the weights of the participants.

输出格式

In the first line there should be written one integer - the minimal number of canoes that should be hired.

样例

Input
100
9
90
20
20
30
50
60
70
80
90
Output
6

22 人解决,30 人已尝试。

26 份提交通过,共有 68 份提交。

4.7 EMB 奖励。

创建: 16 年,2 月前.

修改: 7 年,1 月前.

最后提交: 2 月前.

来源: POI 1997 III Stage

题目标签