# Swimming pool (2) P44496

Statement

thehtml

There are plenty of guided activities in a certain swimming pool. Therefore, the usage rules are very strict:

• The free time slots are only one minute long.
• After using a free slot, we must wait for at least x seconds before using another slot.

You have the list of free slots, and you want to swim for at least m minutes. What is the maximum x that allows it?

Input

Input consists of several cases. Every case begins with the number of minutes m and the number of slots n, followed by n triples H:M:S, indicating that there is a lane that is free for one minute starting at H:M:S. Assume 2 ≤ mn ≤ 1000, that the hours are between 00:00:00 and 23:59:00, and that there are no overlaps between time slots. The final entry is marked with a special case with m = n = 0.

Output

For every case, print the maximum x that permits a total bath time of m or more minutes.

Public test cases
• Input

```2 2
00:00:00  00:01:00
2 2
00:00:00  00:10:03
2 3
10:10:00  00:10:00  00:20:00
3 4
23:00:00  22:00:00  21:00:00  20:00:00
4 8
00:10:40  00:35:30  01:00:00  01:55:00
02:10:00  03:15:00  12:00:20  23:59:00
0 0
```

Output

```0
543
35940
3540
11000
```
• Information
Author