Задачи
Рюкзак
Рюкзак
Вася собрался в поход с друзьями-программистами и решил ответственно подойти к выбору того, что он возьмёт с собой. У Васи есть 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