How much can he sleep? P13289


Statement
 

pdf   zip

thehtml

[r]

Richi is a student with notable characteristics, one of which is his habit of sleeping. Now he is planning one of his usual travels, with many activities, to which he will assist even if they overlap. During his spare time he wants to sleep, but he has decided that only if he can do it for exactly 8 hours (sleeping for less time would be silly). If, when he wakes up, he can sleep for exactly 8 more hours, he will keep sleeping, and so on. How many hours can he sleep in total?

Input

Input consists of several cases. Each case begins with the starting time of the trip s and the ending time of the trip ‍e, two natural numbers such that s < e ≤ 108. Then comes the number of activities ‍n, followed by n descriptions of activities in any order: two natural numbers a and b separated by a hyphen, and such that sa < be. Input ends with two zeros. Suppose n ≤ 105.

Output

For every test case, print a line with the case number and how many hours Richi can sleep, following the format of the sample output.

Public test cases
  • Input

    0 100
    4
    8 - 16
    24 - 27
    34 - 56
    65 - 85
    
    0 100000000
    0
    
    0 99999999
    0
    
    10 25
    1
    17 - 18
    
    10000000 20000000
    4
    12000000 - 18989890
    18989898 - 20000000
    10000015 - 14000000
    10000025 - 10000075
    
    0 0
    

    Output

    #1: 32
    #2: 100000000
    #3: 99999992
    #4: 0
    #5: 16
    
  • Information
    Author
    Noldorin from Aman
    Language
    English
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++ Python
    User solutions
    C++ Python