Swimming pool (2) P44496


Statement
 

pdf   zip

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
    Salvador Roura
    Language
    English
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++