Рюкзак

Вася зібрався у похід з друзями-програмістами і вирішив відповідально підійти до вибору того, що він візьме з собою. У Васі є $n$ речей, які він міг би взяти з собою у рюкзаку. Кожна річ важить 1 кілограм. Речі мають різну "користність" для Васі.

Похід очікується досить тривалий, і Вася хотів би носити рюкзак вагою не більше $w$ кілограм.

Допоможіть йому визначить максимальну сумарну "корисність" предметів у нього в рюкзаку при вазі рюкзака не більше $w$ кілограм.

Вхідні дані

У першому рядку знаходяться цілі числа $w$ і $n(1\le w,n\le 20)$. У другому рядку записано $n$ цілих чисел $c_i(1\le c_i\le 1000)$ — "корисність" кожної з речей.

Вихідні дані

Виведіть максимальну сумарну "корисність" предметів, які Вася може взяти з собою.

Приклади