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

• 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 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

Example
For the text file KAN.IN:

100
9
90
20
20
30
50
60
70
80
90

6