该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem Description

New Year’s Day is coming, and the student council has tasked Lele with distributing souvenirs at the New Year’s party. To keep the value of souvenirs received by participants relatively balanced, he wants to group the purchased souvenirs by price. Each group can contain at most two souvenirs, and the sum of prices in a group cannot exceed a given integer $w$. To finish the distribution as quickly as possible, Lele wants to minimize the number of groups.

Your task is to write a program that finds a grouping scheme with the minimal number of groups and outputs that minimal number.

Input Format

A total of $n+2$ lines:

• The first line contains an integer $w$, the upper bound on the sum of prices in each group.
• The second line contains an integer $n$, the total number of souvenirs.
• Lines 3 to $n+2$: each line contains a positive integer $P_i$ representing the price of the corresponding souvenir.

Output Format

A single integer: the minimal number of groups.

100 
9 
90 
20 
20 
30 
50 
60 
70 
80 
90

6

Hint

Constraints:

• $50\%$ of the testdata: $1 \le n \le 15$.
• $100\%$ of the testdata: $1 \le n \le 3\times 10^4$, $80 \le w \le 200$, $5 \le P_i \le w$.

Translated by ChatGPT 5