Description

New Year's Day is approaching, and the student union has assigned Lele the task of distributing souvenirs for the New Year's party. To ensure that the souvenirs received by the students are relatively balanced in value, he needs to group the purchased souvenirs by price. Each group can contain at most two souvenirs, and the sum of prices in each group cannot exceed a given integer. To ensure that all souvenirs are distributed in the shortest possible time, Lele wants to minimize the number of groups.
Your task is to write a program to find the grouping scheme with the minimum number of groups and output this minimum number.

Input Format

The input consists of $n+2$ lines:
The first line contains an integer $w$, which is the upper limit for the sum of prices in each group.
The second line contains an integer $n$, representing the total number of souvenirs purchased.
Lines $3$ to $n+2$ each contain a positive integer $P$ representing the price of the corresponding souvenir.
50% of the data satisfies: $1 ≤ n ≤ 15$.
100% of the data satisfies: $1 < n ≤ 3 × 10^4$, $80 < w ≤ 200$, $5 ≤ P_i ≤ w$.

Output Format

A single integer representing the minimum number of groups.

Sample

100
9
90
20
20
30
50
60
70
80
90

6