eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Рюкзак

Рюкзак

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

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

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

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

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

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

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

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

Пример

Входные данные #1
2 3
1 5 3
Выходные данные #1
8
Входные данные #2
3 2
3 2
Выходные данные #2
5
Источник Китёнок 2011 г. Ковров