Swimming pool (2) P44496


Statement
 

pdf   zip

html

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

    0
543
35940
3540
11000
    • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++