На производстве штучных изделий детали планируется обработать на станке и на печи для нанесения покрытия. Для каждой детали известна необходимое время для последующей работы: длительность для обработки на станке и длительность обработки на печи. Детали пронумерованы начиная с единицы. Параллельная обработка деталей не предусмотрена.
На конвейерной ленте имеется K мест для деталей, места пронумерованы начиная с единицы. Все детали располагают на ленте по следующему алгоритму:
– все 2N чисел, обозначающих длительность обработки на станке и на печи для N деталей, упорядочивают по возрастанию;
– если минимальное число в этом упорядоченном списке – это длительность обработки на станке конкретной детали, то деталь размещают на конвейерной ленте на первое свободное место от её начала;
– если минимальное число – это длительность обработки на печи, то деталь размещают на первое свободное место от конца ленты транспортёра;
– если число обозначает время обработки на станке или печи той детали, которая уже находится на ленте, то её обработка досрочно завершается и эту деталь убирают с ленты;
– любые размещения деталей на ленту можно производить только при наличии свободных мест.
Определите количество деталей, которые пройдут обработку на станке, а также номер последней детали, которая будет убрана с ленты.
Входные данные
В первой строке входного файла находятся два натуральных числа N и K (K ≤ 1000, N > K) – количество деталей и количество мест на конвейерной ленте. Числа N и K могут быть не равны. Следующие N строк содержат пары чисел, обозначающих соответственно необходимое время для обработки на станке и время для обработки на печи конкретной детали (все числа различные).
Запишите в ответе два натуральных числа: сначала число обработанных деталей на станке, затем – номер последней убранной с ленты детали.
Типовой пример организации данных во входном файле
5 4
30 50
100 155
150 170
10 160
120 55
При таких исходных данных детали 1, 2, 3 и 4 будут обработаны на станке. Деталь 3 будет самой последней деталью, обработка которой досрочно завершится.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.