Рюкзак#2103
Вася планує піти в похід з іншими програмістами і вирішив відповідально підійти до вибору речей. У Васі є предметів, які він може взяти в рюкзак. Кожен предмет важить кілограм, але для Васі вони мають різну "корисність".
Похід буде дуже довгим, тому Вася хоче взяти рюкзак, вага якого не перевищує кілограмів.
Допоможіть йому визначити максимальну сумарну "корисність" предметів у його рюкзаку, якщо вага не може перевищувати кілограмів.
У першому рядку містяться два цілих числа та (1 \leq w, n \leq 20). У другому рядку містяться цілих чисел c_i (1 \leq c_i \leq 1000) — "корисність" кожного предмета.
Виведіть максимальну сумарну "корисність" предметів, які Вася може взяти з собою.
Приклад 1
Приклад 2