В камере хранения имеется K ячеек, пронумерованных от 1 до K. Каждая ячейка в каждый момент может содержать багаж только одного клиента. До начала наблюдения все ячейки свободны.
Для каждой заявки известны её уникальный идентификатор, время прибытия клиента и время освобождения занятой им ячейки. Клиенты обрабатываются в порядке возрастания времени прибытия. При одинаковом времени раньше обрабатывают заявку с меньшим идентификатором.
При прибытии клиенту предоставляют свободную ячейку с наименьшим номером. Если свободных ячеек нет, заявка отклоняется: клиент не ждёт, и его заявка больше не рассматривается. Ячейка, освобождаемая в момент t, уже может быть выдана клиенту, прибывшему в момент t.
Продолжительность хранения по принятой заявке равна времени освобождения минус время прибытия. Для каждой ячейки суммируются полные продолжительности хранения по всем принятым в неё заявкам.
Определите количество принятых заявок и номер ячейки с наибольшей суммарной продолжительностью хранения. Если таких ячеек несколько, выберите ячейку с наименьшим номером.
Входные данные
В первой строке файла записаны два натуральных числа: N — количество заявок, не превышающее 1 000 000, и K — число ячеек, не превышающее 30. Каждая из следующих N строк содержит три натуральных числа: ID заявки, время прибытия и время освобождения. Все эти числа не превышают 1 000 000; время освобождения строго больше времени прибытия. Время задано в секундах от общего начала отсчёта.
Идентификаторы заявок уникальны. Строки файла расположены в произвольном порядке. Числа в строке разделены пробелами. Гарантируется, что хотя бы одна заявка будет принята.
Выходные данные
В ответе запишите сначала количество принятых заявок, затем номер ячейки с наибольшей суммарной продолжительностью хранения.
Типовой пример организации данных
6 2
1 1 5
2 2 6
3 3 4
4 5 10
5 6 8
6 8 12
В примере заявка 3 отклоняется. Заявки 1 и 4 занимают ячейку 1 суммарно на 9 секунд, а заявки 2, 5 и 6 — ячейку 2 суммарно на 10 секунд. Ответ к примеру: 5 2. Пример имеет иллюстративный характер; для решения используйте прилагаемый файл.
Формат записи ответа
При решении задания в эмуляторе станции КЕГЭ ответ записывается в таблицу справа. Каждое число в отдельную ячейку: первое число записывается в первую ячейку строки, второе - во вторую ячейку строки.
При решении вне станции в строку ответа вводятся два числа в указанном порядке через один пробел.