UOJ Logo

NOI.AC

1S 512MB

#995. 新年礼物

Statistics

P1085 新年礼物

元旦到了,小明负责给参加表演的同学发奖品,奖品的价值不同,每个同学可以有一到两个奖品,为了保证每个同学拿到的奖品价值差不多,先要将奖品分组。分组要求,每组最多两件纪念品,每组纪念品的价格之和不能超过一个给定的整数,分组的数目最少。

【输入说明】

输入数据有n+2行:第1行一个整数w,为每组纪念品价格之和的上限。第2行为一个整数n(5<=n<=1000),表示购来的纪念品的总件数。第3~n+2行每行包含一个正整数pi (5 <= pi <= w),表示所对应纪念品的价格

【输出说明】

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

【输入样例】

80
5
12
8
52
74
54

【输出样例】

3

样例说明

74元的一组,54元和8元的一组,52元和12元的一组。