Рюкзак і валіза

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

Софiя розклала всi свої речi в порядку зменшення їх цiнностi та починає складати най-
бiльш цiннi речi в рюкзак. Вона дiє таким чином: бере найцiннiший предмет, i якщо його

маса не перевищує S, то кладе його в рюкзак, iнакше кладе його у валiзу. Потiм вона бере
наступний за цiннiстю предмет, якщо його можна покласти в рюкзак, тобто якщо його маса
разом з масою вже покладених в рюкзак речей не перевищує S, то кладе його в рюкзак,
iнакше − у валiзу. I таким же чином процес триває для всiх предметiв в порядку спадання
їх цiнностi.
Визначте вагу рюкзака та валiзи пiсля того, як Софiя складе всi речi.

Формат вхiдних даних
Перший рядок вхiдних даних мiстить число S − максимально дозволену вагу рюкзака.
У другому рядку вхiдних даних записано число N − кiлькiсть предметiв.
У наступних N рядках записанi маси предметiв, самi предмети перерахованi в порядку
спадання цiнностi (спочатку вказана маса найцiннiшого предмета, потiм маса другого по
цiнностi предмета i так далi). Усi числа натуральнi,

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

Приклад

тест вiдповiдь 18 8

20
5
6
10
5
2
3

0

	Комментарий модератора
	Мне надоело переводить Ваши темы на Русский язык. Эту тему закрываю.

0