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}