Перебуваючи у Лондоні, Вася накупив собі, рідним та друзям багато різноманітних сувенірів та подарунків. Проте, коли він купував у аеропорту квиток на дорогу додому, то з великим подивом довідався, що загальна вага його багажа не повинна перевищувати m грам.
Знаючи кількість придбаних сувенірів та подарунків Васею, допоможіть йому сукомплектувати свій багаж таким чином, щоб він був якомога ближче до граничного і, звичайно ж, не перевищував обмежень для авіарейсу.
У першому рядку задано обмеження на багаж для авіарейсу m (1 ≤ m ≤ 10000) та кількість предметів у Васі n (1 ≤ n ≤ 300).
У другому рядку знаходиться n чисел - відповідна вага кожного з предметів Васі. Відомо, що вага кожного з предметів не перевищує 100000 грам.
Виведіть єдине число - максимально допустиму васу васиного багажа.