Olympic luggage#3613
While staying in London, Vasya bought a large number of various souvenirs and gifts for himself, his relatives, and his friends. However, when purchasing a return flight ticket at the airport, he learned with great disappointment that the total weight of his luggage must not exceed grams.
Given the number of souvenirs and gifts purchased by Vasya, help him pack his luggage so that its total weight is as close as possible to the specified limit and, of course, does not exceed the allowed restriction for the flight.
The first line contains the luggage weight limit for the flight m~(1 \le m \le 10000) and the number of items Vasya has n~(1 \le n \le 300).
The second line contains numbers — the weights of Vasya's items. It is known that the weight of each item does not exceed 10^5 grams.
Print the maximum possible total weight of Vasya's luggage that does not exceed the given limit.
Example 1
Example 2