Задача #1919

(М. Попков) В супермаркете проводится акция по следующим правилам:

− каждый третий товар ценой больше 350 рублей продается за четверть цены;

− общая цена покупки со скидкой округляется вверх до целого числа рублей;

− порядок товаров в чеке определяет магазин и делает это так, чтобы общая сумма скидки была наименьшей.

Покупатель расположил товары на ленте так, чтобы заплатить за покупку несколькими чеками как можно меньше с учетом проходящей акции.

Входные данные

В первой строке входного файла находится число N – количество товаров, которые хочет оплатить покупатель (натуральное число, не превышающее 10 000). В следующих N строках находятся числа, обозначающие цены товаров, которые выбрал покупатель (все числа натуральные, на превышающие 10 000), каждое – в отдельной строке.

Цены товаров указаны в произвольном порядке.

Запишите в ответе два целых числа: сначала сумму, которую заплатит покупатель, а затем сумму, которую он заплатит, если купит все товары одним чеком.

Типовой пример организации данных во входном файле

9

10

20

30

360

370

380

390

400

410

В данном случае товары с ценой 10, 20, 30 не участвуют в акции. Остальные 6 товаров покупатель оплатит двумя разными чеками. В первом – 410, 400, 390; во втором – 380, 370, 360. Под акцию попадут товары с ценой 390 и 360. Сумма первого чека: 410 + 400 + 390 * 0,25 = 907,5 = 908 (магазин округляет вверх), а второго чека: 380 + 370 + 360 * 0,25 = 840. Итого: 908 + 840 + 10 + 20 + 30 = 1808. При покупке одним чеком стоимость составит 1823.