Problems
Knapsack
Knapsack
Find the maximum weight of gold that can be carried in a knapsack with a capacity of $s$, if $n$ gold bars are given with specified weights.
\InputFile
The first line contains one number $s\:(1 \le s \le 10^4)$ --- the knapsack capacity. Then given $n\:(1 \le n \le 300)$ non-negative integers, not exceeding $10^5$ --- the weights of bars.
\OutputFile
Print the maximum weight of gold that can be carried in the knapsack.
\includegraphics{https://static.e-olymp.com/content/32/3205f6221ed071b35e045a3d14c7b363a465287a.gif}
Input example #1
10 1 4 8
Output example #1
9
Input example #2
20 5 7 12 18
Output example #2
19