В магазине проводят акция – каждый второй товар со скидкой 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.
