Huseyn and knapsack

Olympic luggage


Being in London, Vasya bought for his family and friends a lot of all sorts of souvenirs and gifts. However, buying a ticket at the airport on the way back, he was very disappointed to know that the total weight of baggage should not exceed m grams.

Knowing the number of souvenirs and gifts bought by Vasya, help him to pack the luggage so that it will be as close as possible to the limit and, of course, did not exceed limit for the flight.


The first line contains a weight restriction on luggage for the flight m (1m10000) and the number of items n (1n300) Vasya has.

The second line contains n numbers - the weight of each Vasya's item. It is known that the weight of each object is not more than 100000 grams.


Print one number - the maximum possible weight of Vasya's luggage.

Time limit 1 second
Memory limit 128 MiB
Input example #1
6 4
2 7 1 1
Output example #1
Input example #2
15 4
5 7 10 12
Output example #2
Source II Открытая Дистанционная Олимпиада 2012-2013 им. В.Л.Дидковского