Задача №114183. Пакуем чемоданы!

Алёна собирает вещи в отпуск. С собой в самолёт она может взять ручную кладь и багаж. Для ручной клади у Алёны есть рюкзак, а для багажа – огромный чемодан. По правилам перевозки масса ручной клади не должна превосходить \(S\) кг, а багаж может быть любой массы (за сверхнормативный багаж Алёна готова доплатить). Разумеется, наиболее ценные вещи – ноутбук, фотоаппарат, документы и т. д. – Алёна хочет положить в ручную кладь. Алёна разложила все свои вещи в порядке уменьшения их ценности и начинает складывать наиболее ценные вещи в рюкзак. Она действует следующим образом – берёт самый ценный предмет, и если его масса не превосходит \(S\), то кладёт его в рюкзак, иначе кладёт его в чемодан. Затем она берёт следующий по ценности предмет, если его можно положить в рюкзак, то есть если его масса вместе с массой уже положенных в рюкзак вещей не превосходит \(S\), то кладёт его в рюкзак, иначе в чемодан, и таким же образом процесс продолжается для всех предметов в порядке убывания их ценности. Определите вес рюкзака и чемодана после того, как Алёна сложит все вещи.

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

Первая строка входных данных содержит число \(S\) – максимально разрешённый вес рюкзака. Во второй строке входных данных записано число \(N\) – количество предметов. В следующих \(N\) строках даны массы предметов, сами предметы перечислены в порядке убывания ценности (сначала указана масса самого ценного предмета, затем масса второго по ценности предмета и т. д.). Все числа натуральные, число \(S\) не превосходит \(2×10^9\) , сумма весов всех предметов также не превосходит \(2×10^9\) . Значение \(N\) не превосходит \(10^5\).

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

Программа должна вывести два числа – вес рюкзака и вес чемодана (вес пустого рюкзака и чемодана не учитывается).

Система оценивания

Решение, правильно работающее только для случаев, когда все входные числа не превосходят 100, будет оцениваться в 40 баллов.

Примеры
Входные данные
20
5
6
10
5
2
3
Выходные данные
18 8
Сдать: для сдачи задач необходимо войти в систему