Bessie's Weight Problem

Bessie the cow, like so many of her sisters, has put on a few pounds enjoying the delicious grass in Farmer John's pastures. Farmer John has now put her on a strict diet of no more than $H$ ($5 \le H \le 45000$) kilograms of hay per day.

Bessie can eat only whole haybales: once she starts a bale she cannot stop, so she finishes it. She has a list of the $N$ ($1 \le N \le 500$) haybales available for tonight's dinner and, naturally, wants to maximize the total amount of hay she eats. She can eat each listed bale at most once. (Equal weights may appear several times in the list, and each such bale may be eaten once.)

Given the weights $W_i$ ($1 \le W_i \le H$) of the haybales, determine the maximum total weight of hay Bessie can eat without exceeding her limit of $H$ kilograms.

• Line 1: two space-separated integers $H$ and $N$.
• Lines 2 to $N+1$: line $i+1$ contains a single integer $W_i$, the weight of haybale $i$.

• Line 1: a single integer, the maximum number of kilograms of hay Bessie can eat without going over her limit.

With four haybales of weight 15, 19, 20, and 21 and a limit of 56, Bessie can eat the bales weighing 15, 20, and 21 for a total of $15 + 20 + 21 = 56$, reaching the limit exactly.