Problem Description

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.

Input Format

The first line contains two integers, representing $W$ and $N$.

The next $N$ lines each contain a positive integer $G_i$.

Output Format

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

20 5
7
5
4
18
1

19

Hint

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

Translated by ChatGPT 5