Задача #189

(М. Ишимов) Семья М. собирается купить билеты на самолет, чтобы полететь на отдых. Они выбрали рейс с двухэтажным самолётом. В семье, помимо папы и мамы, имеется двое детей, и билеты нужно купить так, чтобы вся семья летела в одном ряду. Каждый из них боится высоты, поэтому места у окон покупать нельзя. Места у окон считаются самые крайние места в каждом ряду (первое и последнее).

Известно, какие места уже заняты. Найдите ряд с наибольшим номером, в котором можно забронировать подходящие места для всей семьи. Гарантируется, что есть хотя бы один ряд, удовлетворяющий этому условию. В ответе запишите два числа: максимальный номер ряда и общее количество таких рядов, в которых можно забронировать подряд идущие свободные места без мест у окон.

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

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

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

7 6

1 50 2

2 23 1

1 50 6

1 1 1

2 30 5

2 23 6

1 1 6

При таких исходных данных есть два подходящих ряда: 1-й ряд на 1-м этаже и 23-й ряд на 2-м этаже. Ответ: 23 2.