eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Олимпийский багаж

Олимпийский багаж

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
prb3613

Пребывая в Лондоне, Вася накупил себе, родным и друзьям множество всевозможных сувениров и подарков. Однако, покупая в аэропорту билет на обратную дорогу, он с большим разочарованием узнал, что общий вес его багажа не должен превышать mграмм.

Зная количество купленных сувениров и подарков Васей, помогите ему упаковать свой багаж таким образом, чтобы он был как можно ближе к предельному и, естественно, не превышал ограничений для авиарейса.

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

В первой строке задано ограничение на багаж для авиарейса m (1m10000) и количество предметов у Васи n (1n300).

Во второй строке находится n чисел - соответственно вес каждого из предметов Васи. Известно, что вес каждого предмета не превышает 100000 грамм.

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

Выведите единственное число - максимально допустимый вес Васиного багажа.

Пример

Входные данные #1
6 4
2 7 1 1
Выходные данные #1
4
Входные данные #2
15 4
5 7 10 12
Выходные данные #2
15
Источник II Открытая Дистанционная Олимпиада 2012-2013 им. В.Л.Дидковского