В супермаркете проводится акция «каждый седьмой товар в чеке за полцены». Покупатель расположил товары на ленте так, чтобы заплатить за покупку двумя чеками как можно меньше с учетом проходящей акции. Однако выяснилось, что программа для кассового аппарата не учитывает расположение товаров на ленте и сортирует цены товаров в чеке таким образом, чтобы стоимость покупки в рублях была максимально возможной. Тогда он расположил товары по-другому.
Входные данные
В первой строке входного файла находится число N – количество товаров, которые хочет оплатить покупатель (натуральное число, не превышающее 10 000). В следующих N строках находятся числа, обозначающие цены товаров, которые выбрал покупатель (все числа натуральные, на превышающие 10 000), каждое – в отдельной строке. Цены товаров указаны в произвольном порядке.
Запишите в ответе два целых числа: сначала сумму, которую заплатит за покупку двумя чеками, а затем сумму, которую он бы заплатил за товары одним чеком.
Типовой пример организации данных во входном файле
5
80
30
50
40
90
При таких исходных данных, если «каждый второй товар в чеке за полцены», суммы в двух чеках и в одном равны соответственно 235 и 255.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.