Le pays d'IOI est composé de $N$ villes numérotées de la ville $1$ à la ville $N$, et les villes sont reliées entre elles par des routes. Il y a $K$ routes dans le pays d'IOI, et chaque route relie $2$ villes distinctes. Les voitures peuvent circuler librement dans les deux sens sur les routes, mais il est impossible d'aller d'une ville à une autre autrement que par les routes.

JOI-kun, qui habite dans la ville $1$ du pays d'IOI, a décidé de se rendre en taxi chez sa grand-mère qui habite dans la ville $N$. Dans le pays d'IOI, il existe $N$ compagnies de taxi, de la compagnie de taxi $1$ à la compagnie de taxi $N$. Les compagnies de taxi du pays d'IOI suivent des règles un peu particulières :

• On ne peut monter dans un taxi de la compagnie de taxi $i$ que dans la ville $i$.
• Le tarif d'un taxi de la compagnie de taxi $i$ est $C_i$, quelle que soit la distance parcourue.
• Un taxi de la compagnie de taxi $i$ ne peut emprunter au maximum que $R_i$ routes consécutives après qu'on y est monté.

Par exemple, si $R_1 = 2$, lorsqu'on monte dans un taxi de la compagnie $1$ depuis la ville $1$, on ne peut emprunter au plus que $2$ routes ; ainsi, pour emprunter $3$ routes ou plus, il est nécessaire de changer de taxi dans une ville intermédiaire.

JOI-kun ne peut ni monter dans un taxi ni en descendre ailleurs que dans une ville. De plus, il ne peut utiliser aucun autre moyen de transport que le taxi. Écrivez un programme pour déterminer le tarif total minimal nécessaire à JOI-kun pour atteindre la ville $N$.

Entrée

L'entrée se compose de $1 + N + K$ lignes.

La $1$-re ligne contient $2$ entiers $N, K$ ($2 \le N \le 5000$, $N - 1 \le K \le 10000$) séparés par un espace. Cela indique que le pays d'IOI est composé de $N$ villes et que le nombre de routes dans le pays d'IOI est $K$.

La $i$-ème ligne ($1 \le i \le N$) des $N$ lignes suivantes contient $2$ entiers $C_i, R_i$ ($1 \le C_i \le 10000$, $1 \le R_i \le N$) séparés par un espace. Cela indique que le tarif d'un taxi de la compagnie $i$ est $C_i$ et qu'il ne peut emprunter au maximum que $R_i$ routes consécutives après qu'on y est monté.

La $j$-ème ligne ($1 \le j \le K$) des $K$ lignes suivantes contient $2$ entiers distincts $A_j, B_j$ ($1 \le A_j < B_j \le N$) séparés par un espace. Cela indique qu'il existe une route entre la ville $A_j$ et la ville $B_j$. Un même couple $(A_j, B_j)$ n'apparaît jamais $2$ fois ou plus.

Dans les données d'entrée fournies, il est garanti qu'il est possible d'aller de n'importe quelle ville à n'importe quelle autre ville en prenant des correspondances de taxis.

Sortie

Affichez sur $1$ ligne un entier représentant le tarif total minimal nécessaire à JOI-kun pour aller de la ville $1$ à la ville $N$.

Exemples

Entrée 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

Sortie 1

700

Remarque

L'exemple ci-dessus correspond à la figure suivante. Les cercles représentent les villes et les lignes représentent les routes.

Dans cet exemple, pour que JOI-kun atteigne la ville $6$ avec un tarif minimal, il procède comme suit :

• Prendre un taxi dans la ville $1$ et aller jusqu'à la ville $5$. (Tarif $400$)
• Prendre un taxi dans la ville $5$ et aller jusqu'à la ville $6$. (Tarif $300$)

Comme le tarif total lorsque JOI-kun emprunte cet itinéraire est $400 + 300 = 700$, on affiche $700$.