Рюкзак

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

Поход предстоит весьма длинный, и Вася хотел бы носить рюкзак весом не более $w$ килограмм.

Помогите ему определить максимальную суммарную "полезность" предметов в его рюкзаке при весе рюкзака не более $w$ килограмм.

Входные данные

В первой строке находятся целые числа $w$ и $n(1\le w,n\le 20)$. Во второй строке записаны $n$ целых чисел $c_i(1\le c_i\le 1000)$ — "полезности" каждой из вещей.

Выходные данные

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

Примеры