시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 5 2 1 25.000%

문제

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, from the standard input,
  • 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 standard output.

입력

In the first line of the standard input 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 ≤ 30,000, 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 of the standard output there should be written one integer — the minimal number of canoes that should be hired.

예제 입력 1

100
9
90
20
20
30
50
60
70
80
90

예제 출력 1

6