박물관 경비원

한 박물관이 경비원들을 위한 매일 반복되는 24시간 근무표를 만들려고 한다. 다음 규칙을 지켜야 한다.

• 각 경비원은 매일 같은 시간대에 근무한다.
• 각 경비원은 자신이 지정한 근무 가능 시간대 안에서만 근무한다.
• 각 경비원은 자신이 지정한 최대 근무 시간(분) 이하로만 근무한다.
• 경비원은 30분 단위 경계에서만 근무를 시작하거나 끝낼 수 있다(예: 04:00이나 04:30은 되지만 04:15은 안 된다).
• 경비원은 어떤 근무 시간 동안 매 순간 근무 가능한 경우에만 그 근무에 배정될 수 있다(예를 들어 어떤 경비원의 근무 가능 시간이 03:05에 시작한다면, 그 경비원은 03:00부터 근무를 시작할 수 없다).

목표는 하루 중 어느 순간이든 근무 중인 경비원 수의 최솟값을 최대화하여 보안을 최대한 강화하는 것이다. 경비원 교대는 순간적으로 이루어진다. 즉, 몇 명이 떠나는 바로 그 순간에 같은 수의 경비원이 도착하면, 교대 중에도 근무 인원 수는 줄어들지 않는다.

입력에는 여러 개의 테스트 케이스가 있다. 각 테스트 케이스는 근무 가능한 경비원의 수 $N$($1 \le N \le 50$)이 담긴 줄로 시작하고, 이어서 경비원마다 하나씩 총 $N$개의 블록이 온다.

각 블록은 두 정수 $K$($1 \le K \le 50$)와 $M$($1 \le M \le 1440$)으로 시작한다. $K$는 경비원의 근무 가능 시간대의 개수이고, $M$은 하루에 근무할 수 있는 최대 시간(분)이다. 이어지는 $K$개의 줄에는 각각 근무 가능 시간대의 시작 시각과 끝 시각이 공백으로 구분되어 주어진다. 이 시간대들은 겹칠 수 있으며, 경비원은 $K$개 시간대의 합집합에 해당하는 시각에 근무할 수 있다.

각 시각은 HH:MM 형식이다($00 \le HH \le 23$, $00 \le MM \le 59$). 자정은 00:00이다. 끝 시각이 시작 시각보다 이르면 그 시간대는 자정을 넘어간다(예를 들어 23:00 03:00은 밤 23:00부터 다음 날 아침 03:00까지 근무 가능함을 뜻한다). 시작 시각과 끝 시각이 같으면 하루 종일 근무 가능하다. 마지막 테스트 케이스 다음에는 0 하나만 있는 줄이 온다.

각 테스트 케이스마다 한 정수를 출력한다. 이는 하루 중 매 순간 근무 중인 경비원이 최소 $k$명이 되도록 하는 유효한 근무표가 존재하는 가장 큰 $k$이다(위에서 설명한 순간적 교대를 가정한다). 답 사이에 빈 줄을 넣지 않는다.