Museum Guards

A museum wants to build a repeating 24-hour daily schedule for its guards, subject to the following rules:

• Each guard works the same time intervals every day.
• Each guard works only within the availability windows they specify.
• Each guard works at most the number of minutes they specify.
• Guards may start or stop working only on half-hour boundaries (for example 04:00 or 04:30, but never 04:15).
• A guard may be assigned a shift only if they are available at every moment of that shift. (For example, if a guard's availability opens at 03:05, they cannot be scheduled starting at 03:00.)

The goal is to make security as strong as possible by maximizing the minimum number of guards on duty at any moment of the day. Guard exchanges are instantaneous: if some guards leave at the exact moment the same number of guards arrive, the coverage does not drop during the exchange.

The input contains several test cases. Each test case begins with a line containing a single integer $N$ ($1 \le N \le 50$), the number of available guards, followed by $N$ blocks, one per guard.

Each block begins with two integers $K$ ($1 \le K \le 50$) and $M$ ($1 \le M \le 1440$): $K$ is the number of availability intervals for the guard, and $M$ is the maximum number of minutes the guard can work per day. The next $K$ lines each contain the start time and end time of one availability interval, separated by whitespace. These intervals may overlap; the guard is available exactly at the union of all $K$ intervals.

Each time is written as HH:MM ($00 \le HH \le 23$, $00 \le MM \le 59$); midnight is 00:00. If the end time is earlier than the start time, the interval wraps past midnight (for example 23:00 03:00 means the guard is available from 23:00 until 03:00 the next morning). If the start and end times are equal, the guard is available the entire day. A line containing a single 0 follows the last test case.

For each test case, output a single integer: the largest $k$ such that there is a valid schedule in which at least $k$ guards are on duty at every moment of the day (with instantaneous exchanges as described above). Print no blank lines between answers.