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

CD

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

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

Предположения:

  • количество треков на CD не превышает 100

  • ни один трек не длится более N минут

  • длина каждого трека выражена целым числом

  • N также целое (0 ≤ N ≤ 200).

Программа должна найти максимально возможную длину записи треков на ленту с соблюдением того же порядка треков, что и на CD.

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

Входные данные содержат несколько строк. В каждой строке сначала задано число N, далее количество треков и длительность звучания каждого трека. Все числа разделены пробелами. Например, в первой строке входных данных первым задано N=5, далее количество треков s=3, первый трек имеет длительность 1 минуту, второй - 3 минуты, и последний - 4 минуты.

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

Выведите строку "sum:" и далее продолжительность записи.

Пример

Входные данные #1
5 3 1 3 4
10 4 9 8 4 2
20 4 10 5 7 4
90 8 10 23 1 2 3 4 5 7
45 8 4 10 44 43 12 9 8 2
Выходные данные #1
sum:5
sum:10
sum:19
sum:55
sum:45