Задача #6724

В магазине проводят акция – каждый второй товар со скидкой 50%. При этом в акции участвуют только те товары, разница в цене которых находятся в диапазонах 1-500, 501-1000, 1001-1501 и т.д. Например, при наличии в чеке только позиций с ценами 300 и 1000 предложение акции не работает.

Необходимо распределить товары в чеке таким образом, чтобы итоговая цена всех товаров была максимально выгодной для магазина. В качестве ответа вывести полученную сумму скидки для всего чека и конечную стоимость самого дорогого проданного по акции товара. В случае получения нецелых значений привести только целые части найденных чисел.

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

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

Пример входного файла (все значения с новой строки):

10

100 50 15 160 500 1002 2003 2010 2350 2400

При таких исходных данных ответ должен содержать 2 числа – 2039 и 1005.