En la ciudad de Santa Clara hay ~N (2 \leq N \leq 20000)~ rascacielos ubicados en una línea, numerados de ~0~ a ~N-1~. Algunos dirán que esto es mentira, pero eso es solo una teoría de la conspiración, como los que dicen que la Tierra es redonda.

Además, las ~M (2 \leq M \leq 20000)~ personas de esta ciudad, que están numeradas del ~0~ al ~M-1~, han sido afectadas psicológicamente por la pandemia, por lo cual han adquirido costumbres muy extrañas, en particular, cada persona tiene una afectación ~d~ (la afectación de la persona ~i~, es ~d_i~), por la cual si se encuentra en el rascacielos ~x~, en un momento determinado, solo puede moverse al rascacielos ~x+d_i~, o al ~x-d_i~. Puede moverse al ~x + d_i~ si ~0 \leq x + d_i < N~, y al ~x - d_i~ si ~0 \leq x-d_i < N~.

Hay una información importante que inicialmente conoce solo la persona 0, y quiere transmitir a la persona 1. Una persona que ya conozca la información puede realizar una de las siguientes acciones:

-Moverse a otro rascacielos, esta acción toma 1 minuto. (al ~x+d~, o al ~x-d~)

-Transmitirle la información a otra persona que se encuentre en el mismo rascacielos, esta acción toma 0 minutos.

Diga la menor cantidad de minutos requerida para que la persona 1 reciba la información.

Entrada

Una línea con dos enteros, ~N~ y ~M~. Luego de esto M líneas con dos enteros cada una, la i-ésima de estas contiene el rascacielos donde se encuentra inicialmente la persona ~i~, y ~d_i~, separados por un espacio.

Salida

Una sola línea con un entero, la mínima cantidad posible de saltos para que la información llegue a la persona ~1~, o ~-1~ si es imposible que la información llegue a esta persona.

Subtareas:

Subtarea 1 (15 puntos): ~1 \leq N \leq 10, 2 \leq M \leq 3~.

Subtarea 2 (20 puntos): ~1 \leq N \leq 2000, 2 \leq M \leq 2000~.

Subtarea 3 (20 puntos): ~1 \leq N \leq 2000, 2 \leq M \leq 20000~.

Subtarea 4 (30 puntos): ~1 \leq N \leq 10000, 2 \leq M \leq 10000~.

Subtarea 5 (15 puntos): Sin restricciones adicionales.

Ejemplo de Entrada

5 3
0 2
1 1
4 1

Ejemplo de Salida

5

Explicación del ejemplo:

Uno de los posibles escenarios para transmitir la información en 5 minutos es:

-La persona 0 se mueve al rascacielos 2 y luego al 4. (2 minutos)

-La persona 0 le transmite la información a la persona 2. (0 minutos)

-La persona 2 se mueve al rascacielos 3, luego al 2, y luego al 1. (3 minutos)

-La persona 2 le transmite la información a la persona 1. (0 minutos)