Задача laying Бізнесмен Петро Петрович збирає речі у відпустку. З собою в літак він може взяти ручну поклажу і багаж. Для ручної поклажі у нього є рюкзак, а для багажу – здоровенна валіза. За правилами перевезення маса ручної поклажі не повинна перевищувати S кг, а багаж може бути будь-якої маси (за наднормативний багаж Петро Петрович готовий доплатити). Зрозуміло, найбільш цінні речі - ноутбук, фотоапарат, документи і т. д. – Петро Петрович хоче покласти в ручну поклажу. Петро Петрович розклав усі свої речі в порядку зменшення їх цінності і починає складати найбільш цінні речі в рюкзак. Він діє в такий спосіб - бере найцінніший предмет, і якщо його маса не перевищує S, то кладе його в рюкзак, інакше кладе його до валізи. Потім він бере наступний за цінністю предмет, якщо його можна покласти в рюкзак, тобто якщо його маса разом з масою вже покладених в рюкзак речей не перевищує S, то кладе його в рюкзак, інакше до валізи, і таким же чином процес триває для всіх предметів в порядку спадання їх цінності. Визначте вагу рюкзака і валізи після того, як Петро Петрович складе всі речі.
Технічні умови. Програма laying читає з пристрою стандартного введення число S (1 ≤ S ≤ 2 × 109) – максимально дозволенa вага рюкзака та число N (1 ≤ N ≤ 105) - кількість предметів. У наступному рядку дано N чисел через пропуски - маси предметів, самі предмети перераховані в порядку спадання цінності (спочатку вказана маса найціннішого предмета, потім маса другого по цінності предмета і т. д.). Всі числа натуральні, сума ваг всіх предметів не перевищує 2 × 109. Програма виводить на пристрій стандартного виведення два числа - вагу рюкзака і вагу валізи (вага порожнього рюкзака і валізи не враховується).
Приклад
|
Введення |
Виведення |
|
10 4 6 3 2 1 |
10 2 |