Задача #6720

На складе лежат пакеты с углём различного веса и стоимости. Вес и стоимость записаны на каждом пакете как натуральные числа: вес не превосходит 100, стоимость не превосходит 10000. Для транспортировки отбираются K пакетов с самой выгодной ценой угля за единицу веса. По заданной информации о пакетах с углём и количестве транспортируемых пакетов определите наибольший возможный вес отправленного угля и стоимость самого большого отправленного пакета.

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

Запишите в ответе два числа – сначала наибольший возможный вес отправленных пакетов, затем стоимость самого большого отправленного пакета.

Пример организации исходных данных во входном файле:

10 4

47 470

50 600

60 480

45 540

30 300

15 180

70 560

30 360

91 910

40 320

При таких исходных данных самая выгодная стоимость у пакетов весом 60, 70, 40; затем – у пакетов весом 91, 30, 47. Поэтому наибольший возможный вес к отправке равен 70+60+40+91 = 261, а стоимость самого большого отправленного пакета равна 910.