P1094 [NOIP 2007 普及组] 纪念品分组

题目背景

NOIP2007 普及组 T2

题目描述

对 $n$ 个整数 $a_i$ 进行分组，每组最多两个数至少一个数，且每组数的和不超过 $w$ 。求最少的分组数目。

输入格式

第一行包括两个整数 $w$， $n$。

下来 $n$ 个整数 $a_i$。

输出格式

一个整数，即最少的分组数目。

样例 #1

样例输入 #1

100 9 
90 20 20 30 50 60 70 80 90

样例输出 #1

6

提示

$50\%$ 的数据满足：$1\le n\le15$。

$100\%$ 的数据满足：$1\le n\le3\times10^4$，$80\le w\le200$，$5 \le P_i \le w$。