Задание 26 ЕГЭ по информатике

Организация планирует закупить $N$ товаров у поставщика. Магазин же, в свою очередь, предоставляет оптовому покупателю скидку на $K$ любых товаров, причем размер скидки варьируется от товара к товару и может различаться. Организация, пользуясь случаем, выбирает, на какие из товаров сделать скидку, таким образом, чтобы заплатить как можно меньше.

Определите сумму, которую заплатит организация за $N$ товаров, а также, при этих же условиях, минимальную возможную стоимость товара, купленного со скидкой.

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

В первой строке входного файла находится два натуральных числа: $N$ ($N ≤ 10 000$) – количество товаров у поставщика и $K$ ($K < N$) – количество товаров, на которые магазин готов сделать скидку. Следующие $N$ строк содержат пары чисел, обозначающих стоимость товара и размер возможной скидки в процентах (от 0 до 100). Каждое из чисел целое, не превосходящее 1000000.

Запишите в ответе два числа: сумму, которую заплатит организация за $N$ товаров, и, при этих условиях, минимальную возможную стоимость товара, купленного со скидкой.

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

7 3

100 20

200 55

150 50

700 50

50 80

125 88

800 80

При таких исходных данных организация купит товары {125, 88}, {800, 80} и {700, 50} со скидкой. Ответ: 1025 125.

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

Файл к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/11681_26.txt