Резервные копии сервера
Сервер принимает данные от клиентских устройств. Каждый запрос на передачу данных регистрируется в журнале работы сервера: записываются время регистрации, идентификатор клиентского устройства и объём данных. Сами данные сохраняются в специальном разделе памяти вместимостью Кбайт; в начале суток раздел пуст.
Запросы выполняются в порядке возрастания времени регистрации. Если для данных очередного запроса в разделе недостаточно свободной памяти, сервер создаёт резервную копию всех накопленных там данных, освобождает раздел и только после этого сохраняет данные запроса. Временем создания резервной копии считается время регистрации этого запроса. Если данные запроса занимают всю свободную память раздела без остатка, резервная копия не создаётся. После последнего запроса резервная копия также не создаётся.
Определите идентификатор клиентского устройства, с которого на сервер передан наибольший общий объём данных, и сумму объёмов (в Кбайт) двух наибольших резервных копий, созданных не позднее 11:59:59.
Входные данные
В первой строке находятся два натуральных числа: — количество строк в журнале () и — вместимость раздела памяти в Кбайт (). Каждая из следующих строк содержит сведения об одном запросе: время регистрации в формате ЧЧ:ММ:СС (часы, минуты, секунды) и два натуральных числа: — идентификатор клиентского устройства () и — объём данных запроса в Кбайт (). Значения в строке разделены пробелами.
Все запросы относятся к одним суткам, время регистрации у всех запросов разное; строки журнала идут в произвольном порядке. Гарантируется, что наибольший общий объём данных передан только с одного устройства и что не позднее 11:59:59 создано не менее двух резервных копий.
Выходные данные
Выведите два целых числа: сначала идентификатор клиентского устройства, с которого передан наибольший общий объём данных, затем сумму объёмов двух наибольших резервных копий, созданных не позднее 11:59:59. Резервные копии одинакового объёма считаются разными.
Примеры
8 140000 01:01:01 101 20000 03:03:03 202 110000 05:05:05 101 90000 07:07:07 303 62000 10:10:10 101 48000 15:15:15 202 12000 21:21:21 303 120000 23:23:23 404 134000
303 220000
3 3 11:59:59 7 2 11:59:57 7 2 11:59:58 7 2
7 4
Примечание
В первом примере копии создаются в 05:05:05, 07:07:07, 21:21:21 и 23:23:23 с объёмами 130 000, 90 000, 122 000 и 120 000 Кбайт. До указанной границы созданы первые две копии, их сумма — 220 000 Кбайт. Клиент 303 передал 182 000 Кбайт — больше любого другого клиента.
Во втором примере запросы сначала нужно упорядочить по времени. При выполнении второго и третьего запросов создаются копии по 2 Кбайт. Копия в 11:59:59 учитывается, поэтому сумма равна 4.