El país de IOI consta de $N$ pueblos numerados desde el pueblo $1$ hasta el pueblo $N$, y los pueblos están conectados entre sí por carreteras. En el país de IOI hay $K$ carreteras, y todas las carreteras conectan $2$ pueblos distintos. Los coches pueden circular libremente en ambos sentidos por las carreteras, pero no es posible ir de un pueblo a otro sin usar las carreteras.

JOI-kun, que vive en el pueblo $1$ del país de IOI, decidió ir en taxi hasta la casa de su abuela, que vive en el pueblo $N$. En el país de IOI hay $N$ compañías de taxis, desde la compañía de taxis $1$ hasta la compañía de taxis $N$. Las compañías de taxis del país de IOI tienen las siguientes reglas un tanto especiales:

• A un taxi de la compañía de taxis $i$ solo se puede subir en el pueblo $i$.
• La tarifa de un taxi de la compañía de taxis $i$ es $C_i$, independientemente de la distancia recorrida.
• Un taxi de la compañía de taxis $i$ puede recorrer como máximo $R_i$ carreteras consecutivas después de subir a él.

Por ejemplo, cuando $R_1 = 2$, si se sube a un taxi de la compañía $1$ desde el pueblo $1$, solo se pueden recorrer como máximo $2$ carreteras, por lo que para recorrer $3$ o más carreteras es necesario hacer transbordo de taxi en algún pueblo intermedio.

JOI-kun no puede subir ni bajar de un taxi en ningún punto que no sea un pueblo. Tampoco puede utilizar ningún medio de transporte distinto del taxi. Escribe un programa para hallar el valor mínimo de la suma de tarifas necesaria para que JOI-kun llegue al pueblo $N$.

Entrada

La entrada consta de $1 + N + K$ líneas.

La $1$-ra línea contiene $2$ enteros separados por un espacio $N, K$ ($2 \le N \le 5000$, $N - 1 \le K \le 10000$). Esto indica que el país de IOI consta de $N$ pueblos y que el número de carreteras del país de IOI es $K$.

La $i$-ésima línea ($1 \le i \le N$) de las siguientes $N$ líneas contiene $2$ enteros separados por un espacio $C_i, R_i$ ($1 \le C_i \le 10000$, $1 \le R_i \le N$). Esto indica que la tarifa de un taxi de la compañía $i$ es $C_i$, y que puede recorrer como máximo $R_i$ carreteras consecutivas después de subir a él.

La $j$-ésima línea ($1 \le j \le K$) de las siguientes $K$ líneas contiene $2$ enteros distintos separados por un espacio $A_j, B_j$ ($1 \le A_j < B_j \le N$). Esto indica que existe una carretera entre el pueblo $A_j$ y el pueblo $B_j$. El mismo par $(A_j, B_j)$ no aparece escrito $2$ o más veces.

En los datos de entrada proporcionados, se garantiza que es posible ir de cualquier pueblo a cualquier otro haciendo transbordos en taxi.

Salida

Imprime en $1$ línea un entero que represente la suma mínima de tarifas necesaria para que JOI-kun vaya del pueblo $1$ al pueblo $N$.

Ejemplos

Entrada 1

6 6
400 2
200 1
600 3
1000 1
300 5
700 4
1 2
2 3
3 6
4 6
1 5
2 4

Salida 1

700

Nota

El ejemplo anterior corresponde a la siguiente figura. Los círculos representan pueblos y las líneas representan carreteras.

En este ejemplo, para que JOI-kun llegue al pueblo $6$ con la tarifa mínima, hace lo siguiente:

• Toma un taxi en el pueblo $1$ y va al pueblo $5$. (Tarifa $400$)
• Toma un taxi en el pueblo $5$ y va al pueblo $6$. (Tarifa $300$)

Como la suma de las tarifas cuando JOI-kun sigue esta ruta es $400 + 300 = 700$, se imprime $700$.