Il paese di IOI è costituito da $N$ cittadine, numerate dalla cittadina $1$ alla cittadina $N$, collegate tra loro da strade. Nel paese di IOI ci sono $K$ strade e ogni strada collega $2$ cittadine diverse. Le automobili possono muoversi liberamente in entrambe le direzioni lungo le strade, ma non è possibile andare da una cittadina a un'altra senza passare per le strade.

JOI-kun, che vive nella cittadina $1$ del paese di IOI, ha deciso di andare in taxi a casa di sua nonna, che vive nella cittadina $N$. Nel paese di IOI ci sono $N$ compagnie di taxi, dalla compagnia di taxi $1$ alla compagnia di taxi $N$. Le compagnie di taxi nel paese di IOI seguono queste regole un po' particolari:

• Sui taxi della compagnia di taxi $i$ è possibile salire solo nella cittadina $i$.
• La tariffa di un taxi della compagnia di taxi $i$ è $C_i$, indipendentemente dalla distanza percorsa.
• Un taxi della compagnia di taxi $i$, una volta saliti a bordo, può percorrere consecutivamente al massimo $R_i$ strade.

Ad esempio, nel caso $R_1 = 2$, salendo su un taxi della compagnia $1$ dalla cittadina $1$ si possono percorrere al massimo $2$ strade; pertanto, per percorrere $3$ o più strade è necessario cambiare taxi in una cittadina intermedia.

JOI-kun non può salire o scendere da un taxi in un punto diverso da una cittadina. Inoltre, non può utilizzare alcun mezzo di trasporto diverso dal taxi. Scrivi un programma per trovare il valore minimo della tariffa totale necessaria affinché JOI-kun raggiunga la cittadina $N$.

Input

L'input è composto da $1 + N + K$ righe.

La $1$-a riga contiene $2$ interi separati da uno spazio $N, K$ ($2 \le N \le 5000$, $N - 1 \le K \le 10000$). Ciò indica che il paese di IOI è composto da $N$ cittadine e che il numero di strade nel paese di IOI è $K$.

La $i$-esima riga ($1 \le i \le N$) delle successive $N$ righe contiene $2$ interi separati da uno spazio $C_i, R_i$ ($1 \le C_i \le 10000$, $1 \le R_i \le N$). Ciò indica che la tariffa di un taxi della compagnia $i$ è $C_i$ e che, dopo essere saliti, esso può percorrere consecutivamente al massimo $R_i$ strade.

La $j$-esima riga ($1 \le j \le K$) delle successive $K$ righe contiene $2$ interi distinti separati da uno spazio $A_j, B_j$ ($1 \le A_j < B_j \le N$). Ciò indica che esiste una strada tra la cittadina $A_j$ e la cittadina $B_j$. La stessa coppia $(A_j, B_j)$ non compare $2$ o più volte.

Nei dati di input forniti è garantito che sia possibile andare da qualsiasi cittadina a qualsiasi altra cambiando taxi.

Output

Stampa in $1$ riga un intero che rappresenta la tariffa totale minima necessaria a JOI-kun per andare dalla cittadina $1$ alla cittadina $N$.

Esempi

Input 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

Output 1

700

Note

L'esempio sopra corrisponde alla figura seguente. I cerchi rappresentano le cittadine e le linee rappresentano le strade.

In questo esempio, per raggiungere la cittadina $6$ con la tariffa minima, JOI-kun procede come segue:

• Prende un taxi dalla cittadina $1$ e va alla cittadina $5$. (Tariffa $400$)
• Prende un taxi dalla cittadina $5$ e va alla cittadina $6$. (Tariffa $300$)

Poiché la tariffa totale seguendo questo percorso è $400 + 300 = 700$, si stampa $700$.