Landet IOI består av $N$ städer, från stad $1$ till stad $N$, och städerna är förbundna med vägar. Det finns $K$ vägar i landet IOI, och varje väg förbinder $2$ olika städer. Bilar kan färdas fritt i båda riktningarna på vägarna, men man kan inte ta sig från en stad till en annan utan att följa vägarna.

JOI-kun, som bor i stad $1$ i landet IOI, har bestämt sig för att åka taxi till sin mormors hus i stad $N$. I landet IOI finns det $N$ taxibolag, från taxibolag $1$ till taxibolag $N$. Taxibolagen i landet IOI har följande något speciella regler:

• En taxi från taxibolag $i$ kan man bara stiga på i stad $i$.
• Priset för att åka med en taxi från taxibolag $i$ är $C_i$, oavsett hur långt man åker.
• En taxi från taxibolag $i$ kan köra längs högst $R_i$ vägar i följd efter att man har stigit på.

Till exempel, om $R_1 = 2$ och man stiger på en taxi från taxibolag $1$ i stad $1$, kan man köra längs högst $2$ vägar, så för att färdas längs $3$ eller fler vägar måste man byta taxi i en stad längs vägen.

JOI-kun kan inte stiga på eller stiga av en taxi på någon annan plats än i en stad. Han kan inte heller använda något annat färdmedel än taxi. Skriv ett program som beräknar den minsta totala kostnaden som krävs för att JOI-kun ska nå stad $N$.

Indata

Indata består av $1 + N + K$ rader.

Den $1$:a raden innehåller $2$ mellanslagsseparerade heltal $N, K$ ($2 \le N \le 5000$, $N - 1 \le K \le 10000$). Detta anger att landet IOI består av $N$ städer och att antalet vägar i landet IOI är $K$.

Den $i$:te raden ($1 \le i \le N$) av de följande $N$ raderna innehåller $2$ mellanslagsseparerade heltal $C_i, R_i$ ($1 \le C_i \le 10000$, $1 \le R_i \le N$). Detta anger att priset för en taxi från taxibolag $i$ är $C_i$ och att den kan köra längs högst $R_i$ vägar i följd efter påstigning.

Den $j$:te raden ($1 \le j \le K$) av de följande $K$ raderna innehåller $2$ olika mellanslagsseparerade heltal $A_j, B_j$ ($1 \le A_j < B_j \le N$). Detta anger att det finns en väg mellan stad $A_j$ och stad $B_j$. Samma par $(A_j, B_j)$ förekommer inte $2$ eller fler gånger.

I givna indata är det garanterat att det går att ta sig från vilken stad som helst till vilken annan stad som helst genom att byta taxi.

Utdata

Skriv på $1$ rad ut ett heltal som anger den minsta totala kostnaden som krävs för att JOI-kun ska ta sig från stad $1$ till stad $N$.

Exempel

Indata 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

Utdata 1

700

Förklaring

Exemplet ovan motsvarar följande figur. Cirklarna representerar städer och linjerna representerar vägar.

För att JOI-kun i detta exempel ska nå stad $6$ till lägsta möjliga kostnad gör han så här:

• Tar en taxi från stad $1$ och åker till stad $5$. (Kostnad $400$)
• Tar en taxi från stad $5$ och åker till stad $6$. (Kostnad $300$)

Eftersom den totala kostnaden när JOI-kun tar denna rutt är $400 + 300 = 700$, skriver vi ut $700$.