Задача #582

(PRO100 ЕГЭ) В супермаркете проводится акция «каждый шестой товар в чеке за полцены». У покупателя есть 100 000 рублей. Какое максимальное количество товаров может купить покупатель, если он сам выберет расположение товаров в чеке?

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

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

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

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

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

5

4

80

30

50

40

Пример входного файла приведён, для покупателя со ста сорока рублями и для акции «каждый второй товар в чеке за полцены». При таких исходных данных ответом на первый вопрос будет число 5 (Пример расположения товаров в чеке: 40 50 4 80 30, сумма покупки: 40 + 50/2 + 4 + 80/2 + 30 = 139), на второй вопрос число 1 (140 - 139 = 1).

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.