#C. 圣诞礼物

    传统题 20ms 256MiB

圣诞礼物

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

题目描述

圣诞节快到了,作为小学信息技术课的王老师准备给小朋友们发放圣诞礼物。为了使每个学生得到的礼物总价格相对一致,他需要将礼物分成很多组:每组至多有两份礼物,同时每组礼物的价格之和不超过 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

HGNU ACM Training Round #2

未参加
状态
已结束
规则
ACM/ICPC
题目
4
开始于
2021-12-17 19:00
结束于
2021-12-17 21:30
持续时间
2.5 小时
主持人
参赛人数
30