Canoes

Interview

Time limit1sMemory limit128 MB

Summary

Given a canoe weight limit and each participant's weight, find the minimum number of two-person canoes needed to carry everyone.

Level: Medium4 of 10
Topics: Greedy, Two pointers, Sorting, Array
Solved: No attempts yet

Problem

You are organizing a canoe tour. Canoes can be hired at the harbour, and all of them are identical. A single canoe holds at most two people, and the combined weight of the people in it cannot exceed a fixed maximum. To keep the cost as low as possible, you must seat every participant using as few canoes as possible.

Write a program that:

reads the maximum weight a canoe crew may have, the number of participants, and the weight of each participant from standard input,
computes the minimum number of canoes needed to seat every participant under these rules,
writes that result to standard output.

Input

The first line contains one integer $w$ , the maximum weight of a canoe crew ( $80 \le w \le 200$ ). The second line contains one integer $n$ , the number of participants ( $1 \le n \le 30000$ ).

Each of the next $n$ lines contains one integer, the weight of a participant, which is between $5$ and $w$ inclusive.

Output

Print a single integer on the first line: the minimum number of canoes that must be hired.

Examples1

Example 1
Input
```
100
9
90
20
20
30
50
60
70
80
90
```
Expected output
```
6
```