favorite We need a little bit of your help to keep things running, click on this banner to learn more

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.


The first line contains integers w и n (1w, n20). The second line contains n integers ci (1ci1000) - the "usefulness" for each thing.


Print the total "usefulness" of things that Vasya can take with him.

Time limit 1 second
Memory limit 122.17 MiB
Input example #1
2 3
1 5 3
Output example #1
Input example #2
3 2
3 2
Output example #2
Source Китёнок 2011 г. Ковров