P2639 [USACO09OCT] Bessie's Weight Problem G

Like many of her sisters, Bessie has put on too much weight from eating too much delicious grass from Farmer John’s pasture. So Farmer John has put her on a very strict diet. Each day, she may eat no more than $H (5 \le H \le 45,000)$ kilograms of hay. Bessie can eat only whole hay bales; once she starts a bale, she cannot stop until she finishes it. She has a complete list of $N (1 \le N \le 500)$ bales that can be served to her for dinner. Naturally, she wants to eat as much hay as possible. Of course, each bale can be eaten at most once (even if the same weight appears $2$ times in the list, that refers to two distinct bales, and each bale can be eaten at most once). Given a list of bale weights $S_i (1 \le S_i \le H)$, determine the maximum total amount of hay Bessie can eat without exceeding the diet limit (note that once she starts a bale, she must finish that entire bale).

The first line contains two space-separated integers $H$ and $N$. Lines $2$ through $N+1$, where line $i+1$ contains a single integer, give the weight $S_i$ of the $i$-th bale.

Output a single integer, the maximum total kilograms of hay Bessie can eat without exceeding the limit.

#### Input Explanation There are four bales with weights $15, 19, 20$, and $21$. Bessie wants to eat as much as she can within the $56$ kilogram limit. #### Output Explanation Bessie can eat $3$ bales (with weights $15, 20, 21$), reaching exactly her $56$ kilogram limit. Translated by ChatGPT 5