La ciudad de TeraCity tiene ~N~ rascacielos ubicados en una línea numerados convenientemente de izquierda a derecha desde ~0~ hasta ~N-1~. No existen otros rascacielos en la ciudad.

TeraCity está habitada por ~M~ criaturas místicas llamadas “nibble”. Los nibble están numerados de ~0~ hasta ~M-1~. El nibble ~i~ inicialmente reside en el rascacielos ~B_i~. El nibble ~i~ tiene un poder místico, representado con un entero positivo ~P_i~. Este poder místico los capacita para saltar entre rascacielos. En un salto simple, un nibble con superpoder p que se encuentra actualmente en el rascacielos b puede moverse al rascacielos ~b+p~(si ~0 \leq b + p < N~) o al rascacielos ~b-p~ (si ~0 \leq b \leq p < N~).

El nibble ~0~ es el líder de todos ellos. Él tiene una noticia urgente para el nibble ~1~, y quiere que la noticia alcance al nibble ~1~ tan rápido como sea posible. Cualquier nibble que reciba la noticia puede hacer alguna de las siguientes acciones:

• Dar un salto para moverse a uno de los otros rascacielos.

• Comunicar la noticia a otro nibble que se encuentre en el mismo rascacielos.

Ayude a los nibble calculando el número mínimo total de saltos requeridos por todos los nibble para tratar de comunicar la noticia al nibble ~1~.

Entrada

La primera línea de la entrada contiene dos enteros ~N~ y ~M~. Cada una de las próximas ~M~ líneas contiene dos enteros ~B_i~ y ~P_i~.

Salida

Una línea simple conteniendo el número mínimo total de saltos, de lo contrario escriba ~-1~ si esto es imposible.

Ejemplo de Entrada Salida

5 3       
0 2
1 1
4 1

Ejemplo de Salida

5

Explicación

Este es una de las posibles maneras de comunicar la noticia utilizando ~5~ saltos:

• El nibble ~0~ salta al rascacielos ~2~ y entonces al rascacielos ~4~ (2 saltos).

• El nibble ~0~ comunica la noticia al ~2~.

• El nibble ~2~ salta al rascacielos ~3~, y entonces al rascacielos ~2~, y luego al rascacielos ~1~ (3 saltos).

• El nibble ~2~ comunica la noticia al nibble ~1~.

Subtareas

Para cada subtarea, ~0 \leq B_i < N~

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

Subtarea 2 (12 puntos): ~1 \leq N \leq 100~, ~1 \leq P_i \leq 100~, ~2 \leq M \leq 2,000~

Subtarea 3 (14 puntos): ~1 \leq N \leq 2,000~, ~1 \leq P_i \leq 2,000~, ~2 \leq M \leq 2,000~

Subtarea 4 (21 puntos): ~1 \leq N \leq 2,000~, ~1 \leq P_i \leq 2,000~, ~2 \leq M \leq 30,000~

Subtarea 5 (43 puntos): ~1 \leq N \leq 30,000~, ~1 \leq P_i \leq 30,000~, ~2 \leq M \leq 30,000~