В супермаркете проводится акция «каждый товар по цене не более чем S за полцены». Покупатель планирует купить N товаров. Однако выяснилось, что программа для кассового аппарата может сделать скидку не более чем на M товаров.
Входной файл содержит информацию о стоимости каждого товара, планируемого к покупке. Определите минимально возможную сумму за все товары, которую может заплатить покупатель и укажите при этом изначальную стоимость самого дешёвого товара, который он сможет приобрести по акции.
Входные данные
В первой строке входного файла находится число N – количество товаров, которые хочет оплатить покупатель (N ≤ 10 000). Во второй строке находятся два числа S – ограничение цены товара для предоставления скидки и M – ограничение количества товаров, приобретаемых по акции. В каждой из следующих N строк находится одно натуральное число, обозначающее цену товара. Цены товаров указаны в произвольном порядке.
Запишите в ответе два целых числа: сначала минимальную сумму, которую может заплатить покупатель, а затем изначальную стоимость самого дешёвого товара, приобретённого по акции.
Типовой пример организации данных во входном файле
6
45 3
80
30
50
20
40
40
При таких исходных данных условию задачи выгоднее приобрести набор товаров со скидкой стоимостью 30, 40 и 40 соответственно. Минимальная сумма покупки будет равна 205. Изначальная стоимость в этом случае самого дешёвого товара, приобретённого по акции, равна 30.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.