Velociraptors 301 P88665


Statement
 

pdf   zip

thehtml

When you go out from the toilet to go back to class you discover that a group of velociraptors has entered to the classroms and has devoured your classmates. The corridor where you are is closed: running away is impossible. Velociraptors, inside the classroms digesting, will go out at any moment to finish with you. Oh, well! It is known that this kind of things happen sometimes.

The corridor of your high school is represented by a segment of the real line from 0 to 2n−2, with n doors of n classroms, placed over the points 0, 2, 4, …, 2n−2 of the line. The toilet where you are going out from is placed at the point k with 0≤ k ≤ 2n−2 and even k. You as well as the velociraptors take 1 second to cover a distance unit over the line (velociraptors are already satisfied and they are not going to run for a miserable desert).

You are asked to, assuming that you know which velociraptors will go out from the classroms to devour you and the moments of time ti that they will do it, and also assuming that these ones will head for you (wherever you are) as soon as they go out, say how many seconds you can extend your (brief but intense) life time making the right movements.

[r]

We consider that will be very useful to think in space-time diagrams as the one on the right, where it is illustrated a possible situaton for k=6 and n=11, where 3 velociraptors go out from the classroms placed in the points 2, 4 and 14 at the moments 6, 10 and 8 respectively. The correct answer to this case is 13.

Input

A test data contains various cases. Each case starts with three naturals n, m and k, with 0≤ k≤ 2n−2, 1≤ n≤ 108 and 1≤ m ≤ 10000, where n and k are as it is describe in the wording and m is the number of velociraptors. The next m lines of the input contain a pair of numbers ci, ti, where ci is the classroom that has devoured the i-th velociraptor and ti is the moment of time that it will go out for its desert. It is fulfilled that 0≤ ai≤ 2n−2 and 0≤ ti≤ 109 for any i, that ci and ti are even, and that all the ci are different.

Output

For each case, your program must print in a line the time that you can extend your life. As times ti and classrooms are even numbers it is fulfilled that the answer will always be an integer.

Scoring

  • Test1:  ‍45 Points ‍

    Test data with no more than 20 cases with n=m ≤ 100 and where the ci appear sorted (as in the instance 1).

  • Test2:  ‍30 Points ‍

    Test data with no more than 20 cases with n≤ 1000 and m≤ 100 (as in the instances 2 and 3).

  • Test3:  ‍25 Points ‍

    Test data with no more than 20 cases of n≤ 108 and m≤ 104 (as in the instance 4).

Public test cases
  • Input

    5 5 4
    0 0
    2 2
    4 4
    6 2
    8 0
    
    5 5 4
    0 0
    2 2
    4 6
    6 2
    8 0
    
    5 5 4
    0 0
    2 6
    4 6
    6 6
    8 0
    
    5 5 4
    0 20
    2 2
    4 20
    6 20
    8 20
    
    5 5 4
    0 2
    2 20
    4 20
    6 20
    8 0
    
    5 5 4
    0 2
    2 4
    4 0
    6 2
    8 2
    
    5 5 0
    0 2
    2 0
    4 10
    6 10
    8 10
    
    3 3 2
    0 10
    2 10
    4 10
    

    Output

    4
    4
    4
    8
    5
    0
    2
    11
    
  • Input

    11 3 6
    2 6
    4 10
    14 8
    

    Output

    13
    
  • Input

    1000 1 0
    100 100
    
    1000 1 0
    100 98
    
    540 5 482
    508 1064
    392 286
    472 338
    186 818
    62 840
    
    43 2 0
    24 72
    44 44
    
    90 7 18
    68 112
    34 84
    8 16
    82 82
    24 60
    52 152
    36 28
    

    Output

    200
    198
    944
    88
    170
    
  • Input

    50000000 7 67958422
    87401816 62889408
    6968110 151700716
    72342116 155469888
    89165870 73851810
    94055040 7972090
    34446444 32438808
    11204152 4411784
    
    50000000 10 54159472
    16811258 75071762
    82396964 125722710
    45739798 94247702
    8034262 18999860
    36992544 92063428
    87918930 66633664
    82468966 168041758
    40581626 31570418
    50437158 161755152
    19037120 148790458
    

    Output

    47617381
    78714732
    
  • Information
    Author
    Omer Giménez
    Language
    English
    Translator
    Carlos Molina
    Original language
    Spanish
    Other languages
    Spanish
    Official solutions
    C++
    User solutions
    C++