1229: Пакуємо валізи -> Тренування для ТЮІ-2017


Submit solution


Points:5
Time limit:1.5s
Memory limit:64M
Author:

Problem type

Оленка збирає речі у відпустку. З собою в літак вона може взяти ручну поклажу і багаж. Для ручної поклажі у Оленки є рюкзак, а для багажу - здоровенна валіза. За правилами перевезення маса ручної поклажі не повинна перевищувати S кг, а багаж може бути будь-якої маси (за наднормативний багаж Оленка готова доплатити). Зрозуміло, найцінніші речі - ноутбук, фотоапарат, документи і т. д. - Оленка хоче покласти в ручну поклажу. Оленка розклала всі свої речі в порядку зменшення їх цінності і починає складати найбільш цінні речі в рюкзак. Вона діє таким чином - бере найцінніший предмет, і якщо його маса не перевищує S, то кладе його в рюкзак, інакше кладе його в чемодан. Потім вона бере наступний за цінністю предмет, якщо його можна покласти в рюкзак, тобто якщо його маса разом з масою вже покладених в рюкзак речей не перевершує S, то кладе його в рюкзак, інакше у валізу, і таким же чином процес триває для всіх предметів в порядку зменшення їх цінності. Визначте вагу рюкзака і валізи після того, як Оленка складе всі речі.

Формат вихідних даних

Перший рядок вхідних даних містить число S - максимально допустима вага рюкзака. У другому рядку вхідних даних записано число N - кількість предметів. У наступних N рядках дані маси предметів, самі предмети перераховані в порядку зменшення цінності (спочатку вказана маса найціннішого предмета, потім маса другого по цінності предмета і т. д.). Всі числа натуральні, число S не перевищує 2×109, сума ваг всіх предметів також не перевищує 2×109. Значення N не більше 105.

Формат вихідних даних

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

Приклад вхідних даних

20
5
6
10
5
2
3

Приклад вихідних даних

18 8

Comments

There are no comments at the moment.