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, \ldots, 2n-2$ de la recta. El lavabo del que sales está situado en el punto $k$ con $0\leq k \leq 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.

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\leq k\leq 2n-2$, $1\leq n\leq 10^8$ y $1\leq m \leq 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\leq a_i\leq 2n-2$ y $0\leq t_i\leq 10^9$ 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:

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

• Test2:

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

• Test3:

  Pruebas con no más de 20 casos de $n\leq 10^8$ y $m\leq 10^4$ (como el ejemplo 4).