Existe una recta numérica de longitud $N-1$. El objetivo es comenzar en $1$ y llegar a $N$ en el menor tiempo posible. Durante un total de $T$ minutos, ocurre un control cada minuto.

El control en el minuto $t$ se define mediante dos números enteros $l_t$ y $r_t$. Si en el minuto $t+0.5$ tu posición $x$ satisface $(l_t \le x \le r_t)$, fallarás inmediatamente. Si $t > T$, no ocurre ningún control.

Cada minuto, puedes moverte a una casilla adyacente o permanecer en la casilla actual. El objetivo se alcanza inmediatamente al llegar a $N$.

Si existe una forma de llegar a la casilla $N$ sin fallar, imprime el tiempo mínimo posible; de lo contrario, imprime -1.

Entrada

La primera línea contiene la longitud de la recta numérica $N$. $(1 \le N \le 2 \times 10^5)$

La segunda línea contiene el tiempo total durante el cual ocurren los controles $T$. $(1 \le T \le 2 \times 10^5)$

Desde la tercera línea, se proporcionan $T$ líneas, cada una con dos números enteros $l_t$ y $r_t$ separados por un espacio. $(1 \le l_t \le r_t \le N)$

Salida

Imprime el tiempo mínimo. Si no existe, imprime -1.

Ejemplos

Entrada 1

4
4
2 4
1 1
2 2
3 3

Salida 1

4

Entrada 2

5
3
2 5
3 4
1 4

Salida 2

-1