Polish version    English version  
  History of OI -> IV OI 1996/1997 -> Problems


 News
 About Olympic
 History of OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
Stage III - results
Stage II - results
Stage I - results
Problems
Regulations
Organization
Hints
Schedule
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 OI books
 National team
 Olympic camps
 Photo gallery
 Links
 SIO
 MAIN
Niebieskie ksi.eczki
IV Olimpiada Informatyczna 1996/1997

Task: KAJ
Author: Wojciech Rytter
Canoes

III stage contest  
Source fileKAJ.??? (e.g. PAS,C, CPP)
Executable fileKAJ.EXE
Input fileKAJ.IN
Output fileKAJ.OUT

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.

Task

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, from the text file KAJ.IN
  • 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 to the text file KAJ.OUT.

Input

In the first line of the text file KAJ.IN 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.

Output

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

Example
For the text file KAN.IN:

100
9
90
20
20
30
50
60
70
80
90
the correct result is the text file KAJ.OUT:
6





Print friendly version