Задание 26 ЕГЭ по информатике

В период сбора урожая на винограднике работают $N$ сборщиков и $K$ приёмщиков винограда. Каждый сборщик собирает только один сорт винограда: традиционный сорт $A$ или новый сорт $B$. Каждый приёмщик принимает урожай только одного сорта. Всем приёмщикам присвоены номера начиная с единицы. Приёмщики нечётными номерами принимают урожай винограда сорта $A$, чётными - сорта $B$.

Умная камера оценивает количество собранного винограда и определяет время начала и время окончания приёмки партии урожая. Время задаётся в минутах от начала рабочего дня. Приёмщик начинает получение следующей партии винограда от сборщика не ранее, чем через 5 минут после окончания приёмки предыдущей партии. Несколько сборщиков не могут сдавать урожай одному приёмщику в одно и то же время. Автоматизированная система отправляет очередного сборщика к приёмщику данного сорта с минимальным номером. Если в момент прибытия партии урожая свободных приёмщиков нет, то виноград передаётся на рынок для продажи.

Определите максимальное суммарное количество партий винограда обоих сортов, полученных приёмщиками, и номер приёмщика, который последним примет партию урожая.

Входные данные

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

Типовой пример организации данных во входном файле

2 6

30 60 A

65 1000 A

65 1000 В

1010 1300 B

65 900 A

905 1100 A

Пример приведён для двух приёмщиков и шести сборщиков винограда. При таких исходных данных приёмщики получат 5 партий винограда ((30 60 A), (65 900 A), (905 1100 A), (65 1000 В), (1010 1300 В)), одна партия будет отправлена на рынок, последним примет урожай винограда приёмщик с номером 2.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Файл к заданию: https://drive.google.com/file/d/1V8duoTcdUjDFazH6lLwlk10h8igKYTE7/view?usp=drive_link