Problems
Knapsack
Knapsack
Vasya is going to hike with fellow programmers and decided to take a responsible approach to the choice of what he will take with him. Vasya has $n$ things that he could take with him in his knapsack. Every thing weighs $1$ kilogram. Things have different "usefulness" for Vasya.
The hiking is going to be very long, so Vasya would like to carry a knapsack of weight no more than $w$ kilo.
Help him to determine the total "usefulness" of things in his knapsack if the weight of backpack can be no more than $w$ kilo.
\InputFile
The first line contains integers $w$ и $n~(1 \le w, n \le 20)$. The second line contains $n$ integers $c_i~(1 \le c_i \le 1000)$ --- the "usefulness" for each thing.
\OutputFile
Print the total "usefulness" of things that Vasya can take with him.
Input example #1
2 3 1 5 3
Output example #1
8
Input example #2
3 2 3 2
Output example #2
5