CD
Вам предстоит длительное путешествие на автомобиле. К сожалению, у Вас в машине есть только магнитофон, а лучшая музыка записана на компакт дисках. У Вас есть чистая магнитофонная лента с длительностью звучания N минут. Вам нужно выбрать песни для записи на магнитофонную ленту таким образом, чтобы не используемое на ней место было минимально.
Предположения:
- количество треков на CD не превышает 100
- ни один трек не длится более N минут
- длина каждого трека выражена целым числом
- N также целое (0 ≤ N ≤ 200).
Программа должна найти максимально возможную длину записи треков на ленту с соблюдением того же порядка треков, что и на CD.
Технические условия
Входные данные
Входные данные содержат несколько строк. В каждой строке сначала задано число N, далее количество треков и длительность звучания каждого трека. Все числа разделены пробелами. Например, в первой строке входных данных первым задано N=5, далее количество треков s=3, первый трек имеет длительность 1 минуту, второй - 3 минуты, и последний - 4 минуты.
Выходные данные
Выведите строку "sum:" и далее продолжительность записи.
Информация о задаче
Лимит времени: 1 секундаЛимит памяти: 16 MB
Баллы за пройденный тест: 10
Сложность: 30% 16/23
Пример
Пример входных данных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 |
| ← Египет | Список задач | Ходи конём! → |