Оленка збирає речі у відпустку. З собою в літак вона може взяти ручну поклажу і багаж. Для ручної поклажі у Оленки є рюкзак, а для багажу - здоровенна валіза. За правилами перевезення маса ручної поклажі не повинна перевищувати \(S\) кг, а багаж може бути будь-якої маси (за наднормативний багаж Оленка готова доплатити). Зрозуміло, найцінніші речі - ноутбук, фотоапарат, документи і т. д. - Оленка хоче покласти в ручну поклажу. Оленка розклала всі свої речі в порядку зменшення їх цінності і починає складати найбільш цінні речі в рюкзак. Вона діє таким чином - бере найцінніший предмет, і якщо його маса не перевищує \(S\), то кладе його в рюкзак, інакше кладе його в чемодан. Потім вона бере наступний за цінністю предмет, якщо його можна покласти в рюкзак, тобто якщо його маса разом з масою вже покладених в рюкзак речей не перевершує \(S\), то кладе його в рюкзак, інакше у валізу, і таким же чином процес триває для всіх предметів в порядку зменшення їх цінності. Визначте вагу рюкзака і валізи після того, як Оленка складе всі речі.
Формат вихідних даних
Перший рядок вхідних даних містить число \(S\) - максимально допустима вага рюкзака. У другому рядку вхідних даних записано число \(N\) - кількість предметів. У наступних \(N\) рядках дані маси предметів, самі предмети перераховані в порядку зменшення цінності (спочатку вказана маса найціннішого предмета, потім маса другого по цінності предмета і т. д.). Всі числа натуральні, число \(S\) не перевищує \(2 ·10^9\), сума ваг всіх предметів також не перевищує \(2 \cdot 10^9\). Значення \(N\) не більше \(10^5\).
Формат вихідних даних
Програма повинна вивести два числа - вагу рюкзака і вагу валізи (вага порожнього рюкзака і валізи до уваги береться).
Приклад вхідних даних
20
5
6
10
5
2
3
Приклад вихідних даних
18 8
Коментарі