Souvenir Grouping

Problem Background

[NOIP 2007 Junior] Souvenir Grouping — Problem 2.

Problem Description

New Year's Day is coming, and the student union has asked Lele to hand out souvenirs at the evening party. To make the value of the souvenirs each student receives relatively balanced, Lele groups the bought souvenirs by price. However, each group may contain at most two souvenirs, and the sum of the prices in a group must not exceed a given integer. To finish handing out all souvenirs in as little time as possible, Lele wants the number of groups to be as small as possible.

Your task is to write a program that finds, among all grouping schemes, the one with the fewest groups, and outputs this minimum number of groups.

Input Format

There are $n+2$ lines in total:

The first line contains an integer $w$, the upper limit on the sum of prices in each group.

The second line contains an integer $n$, the total number of souvenirs $G$ purchased.

Lines $3\sim n+2$ each contain a positive integer $P_i$, the price of the corresponding souvenir.

Output Format

One integer: the minimum number of groups.

Sample Input

100
9
90
20
20
30
50
60
70
80
90

Sample Output

6

Constraints

For $50\%$ of the data: $1\le n\le 15$.

For $100\%$ of the data: $1\le n\le 3\times10^4$, $80\le w\le 200$, $5 \le P_i \le w$.