eolymp
bolt
Try our new interface for solving problems
Məsələlər

Рюкзак

Рюкзак

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

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