Задача #3089

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

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

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

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

Каждая из следующих N строк описывает одно устройство и содержит 3 целых числа: время поступления устройства в центр (количество минут с начала рабочего дня), время, необходимое для ремонта и номер мастерской, в которую его необходимо направить (0 означает, что ремонт возможен в любой мастерской). Гарантируется, что никакие два устройства не поступают одновременно.

Определите, наибольшее количество устройств, отремонтированных в течении дня в одной мастерской, и количество устройств, которые отправятся на утилизацию из-за слишком больших очередей. В ответе запишите два целых числа: сначала наибольшее количество устройств, отремонтированных в одной мастерской, затем количество утилизированных устройств.