#P130. 圣诞礼物

圣诞礼物

题目描述

圣诞节快到了,作为小学信息技术课的王老师准备给小朋友们发放圣诞礼物。为了使每个学生得到的礼物总价格相对一致,他需要将礼物分成很多组:每组至多有两份礼物,同时每组礼物的价格之和不超过 ww。王老师希望你能编写一个程序,找到所有分组方案中分组的数目最少的一种。

输入格式

第一行输入一个整数 w(80w200)w(80 \le w \le 200),表示每组礼物价格之和的上限,第二行输入一个整数 n(1n30000)n(1 \le n \le 30000),表示购买的礼物的总件数,接下来 nn 行每行输入一个正整数 pi(5piw)p_i(5 \le p_i \le w),表示所对应的礼物的价格。

输出格式

一行,输出最少的分组数目。

样例

100
9
90
20
20
30
50
60
70
80
90
6