Задача #6663

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

Входные данные представлены в файле 26_6663.txt следующим образом. В первой строке входного файла записано натуральное число N – общее количество занятых мест (1 ≤ N ≤ 600 000). В каждой из следующих N строках находятся по три натуральных числа, не превышающих 25 000. Первые два числа – это номер ряда и место в ряду, занятое участником конференции. Если третье число равно 0, то место занято участником из города Н, а если оно равно 1, то участником из другого города.

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

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

15

1 1 0

1 3 1

1 5 0

1 7 1

1 8 0

2 3 1

2 8 1

2 9 0

2 10 0

3 1 0

3 2 1

3 6 1

3 7 0

3 8 0

3 9 0

В примере требуется найти ряд, в котором есть ровно три свободных места между участниками из других городов, а также хотя бы четыре занятых места, занятые участниками из города Н.

В 3-м ряду есть 3 свободных места подряд между участниками из других городов (места 3, 4 и 5) и 4 места заняты участниками из города Н. В этом ряду 2 места заняты участниками из других городов (места 2 и 6). Ответ: 3 2.