Каждый девятый бесплатно
В супермаркете проводится акция «каждый девятый товар бесплатно». Покупатель делит товары на группы по девять и за каждую группу платит отдельным чеком. Оставшиеся товары, если их меньше девяти, оплачиваются без скидки.
Сначала покупатель рассчитывал, что бесплатным будет самый дорогой товар каждой группы: его он собирался класть на девятое место. Товары он делит на группы так, чтобы заплатить как можно меньше.
Однако программа кассового аппарата не учитывает расположение товаров и в каждой группе делает бесплатным самый дешёвый товар. Узнав об этом, покупатель разделил товары на группы по-другому — так, чтобы и в этом случае заплатить как можно меньше.
Определите минимальную сумму, которую покупатель планировал заплатить изначально, и сумму, которую он заплатил на самом деле.
Входные данные
В первой строке находится число — количество товаров (натуральное число, не превышающее ). В каждой из следующих строк находится цена одного товара — натуральное число, не превышающее .
Цены идут в произвольном порядке и могут повторяться.
Выходные данные
Выведите два целых числа: сначала минимальную сумму, которую покупатель планировал заплатить изначально, затем сумму, которую он заплатил на самом деле.
Примеры
10 80 30 50 40 10 10 10 10 10 5
175 245
18 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
136 160
Примечание
В первом примере общая цена равна 255. Изначально можно было получить бесплатно товар за 80, то есть заплатить 175. На деле выгодно объединить девять самых дорогих товаров: касса сделает бесплатным товар за 10, а оставшийся товар за 5 оплачивается полностью. Сумма равна 245.
Во втором примере общая цена равна 171. Планируемая скидка равна , фактическая при оптимальном делении — .