(Е. Джобс) В магазине проводят акция -- каждый второй товар со скидкой 50%. При этом в акции участвуют только те товары, цены которых попадают в одну ценовую категорию. Каждая ценовая категория включает 500 целых значений: 1-500, 501-1000, 1001-1500 и т.д. Например, при наличии в чеке только позиций с ценами 300 и 1000 предложение акции не работает.
Необходимо распределить товары в чеке таким образом, чтобы итоговая цена всех товаров была максимально выгодной для магазина. В качестве ответа вывести полученную сумму скидки для всего чека и конечную стоимость самого дорогого проданного по акции товара. В случае получения нецелых значений привести только целые части найденных чисел.
Входные данные представлены в файле 26-44.txt следующим образом. В первой строке записано натуральное число N -- количество покупаемых товаров (10 ≤ N ≤ 10000). В следующих N строках находятся значения -- стоимость каждого товара (все числа натуральные, не превышающие 10 000), по одному в каждой строке.
Пример входного файла (все значения с новой строки):
10
100 50 15 160 500 1002 2003 2010 2350 2400
При таких исходных данных ответ должен содержать 2 числа -- 2039 и 1005.