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