{"trustable":true,"sections":[{"title":"Background","value":{"format":"MD","content":"NOIP2007 popular group T2"}},{"title":"Description","value":{"format":"MD","content":"New Year\u0027s Day is coming soon, and the school student union has assigned Lele the task of distributing souvenirs for the New Year\u0027s Eve party. In order to ensure that the souvenirs received by the students attending the party have relatively balanced value, he needs to group the purchased souvenirs based on their prices. Each group can include at most two souvenirs, and the total price of souvenirs in each group cannot exceed a given integer. To ensure that all souvenirs are distributed in the shortest possible time, Lele hopes to minimize the number of groups.\n\nYour task is to write a program to find the grouping scheme with the minimum number of groups, and output the minimum number of groups."}},{"title":"Input","value":{"format":"MD","content":"There are $n+2$ lines in total:\n\nThe first line includes an integer $w$, which is the upper limit of the total price of souvenirs in each group.\n\nThe second line is an integer $n$, representing the total number of purchased souvenirs $G$.\n\nThe $3\\sim n+2$th line contains a positive integer $P_i$ representing the price of the corresponding souvenir."}},{"title":"Output","value":{"format":"MD","content":"An integer, which is the minimum number of groups."}},{"title":"Sample 1","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e100 \n9 \n90 \n20 \n20 \n30 \n50 \n60 \n70 \n80 \n90\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"Hint","value":{"format":"MD","content":"The data of $50\\%$ satisfies: $1\\le n\\le15$.\n\nThe data of $100\\%$ satisfies: $1\\le n\\le3\\times10^4$, $80\\le w\\le200$, $5 \\le P_i \\le w$."}}]}