CD
CD
Вам предстоит длительное путешествие на автомобиле. К сожалению, у Вас в машине есть только магнитофон, а лучшая музыка записана на компакт дисках. У Вас есть чистая магнитофонная лента с длительностью звучания N минут. Вам нужно выбрать песни для записи на магнитофонную ленту таким образом, чтобы не используемое на ней место было минимально.
Предположения:
количество треков на CD не превышает 100
ни один трек не длится более N минут
длина каждого трека выражена целым числом
N также целое (0 ≤ N ≤ 200).
Программа должна найти максимально возможную длину записи треков на ленту с соблюдением того же порядка треков, что и на CD.
Входные данные
Входные данные содержат несколько строк. В каждой строке сначала задано число N, далее количество треков и длительность звучания каждого трека. Все числа разделены пробелами. Например, в первой строке входных данных первым задано N=5, далее количество треков s=3, первый трек имеет длительность 1 минуту, второй - 3 минуты, и последний - 4 минуты.
Выходные данные
Выведите строку "sum:" и далее продолжительность записи.
Пример
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
sum:5 sum:10 sum:19 sum:55 sum:45