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

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

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

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

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