Задание 26

Файлы к заданию:

В магазинах города продают сахар различной стоимости на развес. Количество доступного сахара и его общая стоимость для каждого магазина записаны как натуральные числа: вес не превосходит 1000, стоимость не превосходит 100 000. Зинаиде Михайловне и Алле Петровне для консервации необходимо приобрести К килограмм сахара каждой. С целью экономии каждая сперва покупает сахар с самой низкой ценой за один килограмм. Зинаида Михайловна посетила все магазины первой и купила необходимое ей количество, Алла Петровна покупала позже из оставшегося в магазинах. По заданной информации о сахаре в магазинах и необходимом количестве килограмм определите наименьшую сумму, которую потратят на сахар Зинаида Михайловна и Алла Петровна. Входные данные представлены в файле следующим образом. В первой строке через пробел записаны числа N - количество магазинов (натуральное число, не превышающее 1000) и K – требуемый вес сахара (натуральное число, не превосходящее 1000). В каждой из последующих N строк через пробел записаны два числа – количество сахара в магазине и его общая стоимость. Запишите в ответе два числа – наименьшие суммы, которую потратят на сахар Зинаида Михайловна и Алла Петровна. Пример организации исходных данных во входном файле: 10 100 47 4700 50 6000 60 4800 45 5400 30 3000 15 1800 70 5600 30 3600 91 9100 40 3200 При таких исходных данных самая выгодная стоимость у магазинов с весом 60, 70, 40; затем – с весом 91, 30, 47. Зинаида Михайловна купит 60+40 кг за 8000 рублей; Алла Петровна купит 30+40+30 кг за 8600 рублей.