Задача #6675

В магазинах города продают сахар различной стоимости на развес. Количество доступного сахара и его общая стоимость для каждого магазина записаны как натуральные числа: вес не превосходит 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 рублей.