Swimming pool (2) P44496

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 \le m \le n \le 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.