Вася собрался в поход с друзьями-программистами и
решил ответственно подойти к выбору того, что он возьмёт с собой. У Васи есть N
вещей, которые он мог бы взять с собой в рюкзаке. Каждая вещь весит 1
килограмм. Вещи обладают разной «полезностью» для Васи.
Поход предстоит весьма длинный, и Вася хотел бы носить
рюкзак весом не более W килограмм.
Помогите ему определить максимальную суммарную
«полезность» предметов в его рюкзаке при весе рюкзака не более W
килограмм.
В первой строке входных данных находятся целые числа W
и N (1 £ W, N £ 20). Во второй строке через пробел записаны N
целых чисел Ci (1 £ Ci £ 1000) — «полезности» каждой из вещей.
Выведите максимальную суммарную «полезность»
предметов, которые Вася может взять с собой.
|
Пример ввода 1
2
3
1
5 3
Пример вывода 1
8
|
Пример ввода 2
3
2
3
2
Пример вывода 2
5
|
