P10484 Gift Delivery

As a punishment, GY was sent to help a certain “godly cow” deliver gifts to girls (GY: it seems like a good job). However, after GY saw the gifts, he no longer thought so. The cow has $N$ gifts, and they are extremely heavy, but GY is also extremely strong. In one trip, he can carry any number of items as long as the total weight is less than or equal to $W$. GY wants to carry a set of items with total weight as large as possible in one trip. Please tell him the maximum total weight he can carry in one trip within his strength limit.

The first line contains two integers, representing $W$ and $N$. The next $N$ lines each contain a positive integer $G_i$.

Output a single integer, representing the maximum total weight that GY can carry in one trip within his strength limit.

For all testdata, $1 \le N \le 46$, $1 \le W,G[i] \le 2^{31}-1$. Translated by ChatGPT 5