eolymp
Соревнования

Huseyn and knapsack

Рюкзак

Найдите максимальный вес золота, который можно унести в рюкзаке вместительностью s, если есть n золотых слитков с заданными весами.

Входные данные

Первая строка содержит одно число s (1s104). Далее следует n (1n300) неотрицательных чисел, не превосходящих 105 - веса слитков.

Выходные данные

Выведите искомый максимальный вес.

prb4831.gif

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
10
1 4 8
Выходные данные #1
9
Входные данные #2
20
5 7 12 18
Выходные данные #2
19