Velocirráptors 301 P88665

Cuando sales del lavabo para volver a clase descubres que una manada de velocirráptors ha entrado en las aulas y ha devorado a tus compañeros. El pasillo donde estás está cerrado: imposible huir. Los velocirráptors, dentro de las aulas haciendo la digestión, saldrán en cualquier momento para acabar contigo. En fin, ya se sabe que estas cosas pasan.

El pasillo de tu instituto se representa por un segmento de la recta real que va del 0 al 2n−2, con n puertas que dan a n aulas, situadas sobre los puntos 0, 2, 4, …, 2n−2 de la recta. El lavabo del que sales está situado en el punto k con 0≤ k ≤ 2n−2 y k par. Tanto tú como los velocirráptors tardáis 1 segundo en recorrer una unidad de distancia sobre la recta (los velocirráptors ya están satisfechos y no están dispuestos a correr más por un triste postre).

Se te pide que, asumiendo que conoces qué velocirráptors saldrán de sus aulas a por tí y en qué instantes de tiempo t_i lo harán, y asumiendo también que estos se dirigirán hacia ti (estés donde estés) nada más salir, digas cuántos segundos puedes alargar tu (breve pero intenso) tiempo de vida realizando los movimientos acertados.

[r]

Creemos que te resultará muy útil pensar en diagramas espacio-temporales como el de la derecha, donde se ejemplifica una posible situación para k=6 y n=11, donde 3 velocirráptors salen de las aulas situadas en los puntos 2, 4 y 14 en los instantes 6, 10 y 8 respectivamente. La respuesta correcta en este caso es 13.

Entrada

Un juego de pruebas contiene varios casos. Cada caso empieza con tres naturales n, m y k, con 0≤ k≤ 2n−2, 1≤ n≤ 10⁸ y 1≤ m ≤ 10000, donde n y k son como se describe en el enunciado y m es el número de velocirráptors. Las siguientes m líneas de la entrada contienen un par de números a_i, t_i, donde a_i es el aula que se ha zampado el i-ésimo velocirráptor y t_i el instante de tiempo en el que saldrá a por su postre. Se cumple que 0≤ a_i≤ 2n−2 y 0≤ t_i≤ 10⁹ para todo i, que a_i y t_i son pares, y que todos los a_i son distintos.

Salida

Para cada caso, escribe en una línea el tiempo que puedes alargar tu vida. Que los tiempos t_i y las aulas a_i sean números pares garantiza que la respuesta siempre será un entero.

Puntuación

• Test1:  45 Puntos 

  Pruebas con no más de 20 casos con n=m ≤ 100 y donde los a_i aparecen ordenados (como el ejemplo 1).

• Test2:  30 Puntos 

  Pruebas con no más de 20 casos con n≤ 1000 y m≤ 100 (como los ejemplos 2 y 3).

• Test3:  25 Puntos 

  Pruebas con no más de 20 casos de n≤ 10⁸ y m≤ 10⁴ (como el ejemplo 4).