(ПАСКАЛЬ) Задача 3. Пакуем чемоданы!
Алёна собирает вещи в отпуск. С собой в самолёт она может взять ручную кладь и
багаж. Для ручной клади у Алёны есть рюкзак, а для багажа – огромный чемодан.
По правилам перевозки масса ручной клади не должна превосходить S кг, а багаж
может быть любой массы (за сверхнормативный багаж Алёна готова доплатить). Разумеется,
наиболее ценные вещи – ноутбук, фотоаппарат, документы и т. д. – Алёна хочет положить
в ручную кладь.
Алёна разложила все свои вещи в порядке уменьшения их ценности и начинает
складывать наиболее ценные вещи в рюкзак. Она действует следующим образом – берёт
самый ценный предмет, и если его масса не превосходит S, то кладёт его в рюкзак, иначе
кладёт его в чемодан. Затем она берёт следующий по ценности предмет, если его можно
положить в рюкзак, то есть если его масса вместе с массой уже положенных в рюкзак вещей
не превосходит S, то кладёт его в рюкзак, иначе в чемодан, и таким же образом процесс
продолжается для всех предметов в порядке убывания их ценности.
Определите вес рюкзака и чемодана после того, как Алёна сложит все вещи.
Первая строка входных данных содержит число S – максимально разрешённый вес
рюкзака. Во второй строке входных данных записано число N – количество предметов.
В следующих N строках даны массы предметов, сами предметы перечислены в порядке
убывания ценности (сначала указана масса самого ценного предмета, затем масса второго по
ценности предмета и т. д.). Все числа натуральные, число S не превосходит 2×109
, сумма
весов всех предметов также не превосходит 2×109
. Значение N не превосходит 105
.
Программа должна вывести два числа – вес рюкзака и вес чемодана (вес пустого
рюкзака и чемодана не учитывается).
Пример входных и выходных данных
Ввод:
20
5
6
10
5
2
3
Вывод:
18
8