Məsələlər
Рюкзак
Рюкзак
Вася собрался в поход с друзьями-программистами и решил ответственно подойти к выбору того, что он возьмёт с собой. У Васи есть n вещей, которые он мог бы взять с собой в рюкзаке. Каждая вещь весит 1 килограмм. Вещи обладают разной "полезностью" для Васи.
Поход предстоит весьма длинный, и Вася хотел бы носить рюкзак весом не более w килограмм.
Помогите ему определить максимальную суммарную "полезность" предметов в его рюкзаке при весе рюкзака не более w килограмм.
Giriş verilənləri
В первой строке находятся целые числа w и n~(1 \le w, n \le 20). Во второй строке записаны n целых чисел c_i~(1 \le c_i \le 1000) — "полезности" каждой из вещей.
Çıxış verilənləri
Выведите максимальную суммарную "полезность" предметов, которые Вася может взять с собой.
Nümunə
Giriş verilənləri #1
2 3 1 5 3
Çıxış verilənləri #1
8
Giriş verilənləri #2
3 2 3 2
Çıxış verilənləri #2
5