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 ≤ m ≤ n ≤ 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

Information

Author: Salvador Roura
Language: English
Translator: Salvador Roura
Original language: Catalan
Other languages: Catalan
Official solutions: C++
User solutions: C++