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.

Input

The first line contains a weight restriction on luggage for the flight m (1 ≤ m ≤ 10000) and the number of items n (1 ≤ n ≤ 300) 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.

Output

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