Перебуваючи у Лондоні, Вася накупив собі, рідним та друзям багато різноманітних сувенірів та подарунків. Проте, коли він купував у аеропорту квиток на дорогу додому, то з великим подивом довідався, що загальна вага його багажа не повинна перевищувати m грам.

Знаючи кількість придбаних сувенірів та подарунків Васею, допоможіть йому сукомплектувати свій багаж таким чином, щоб він був якомога ближче до граничного і, звичайно ж, не перевищував обмежень для авіарейсу.

Вхідні дані

У першому рядку задано обмеження на багаж для авіарейсу m (1 ≤ m ≤ 10000) та кількість предметів у Васі n (1 ≤ n ≤ 300).

У другому рядку знаходиться n чисел - відповідна вага кожного з предметів Васі. Відомо, що вага кожного з предметів не перевищує 100000 грам.

Вихідні дані

Виведіть єдине число - максимально допустиму васу васиного багажа.