Landet IOI består av $N$ byer, fra by $1$ til by $N$, og byene er knyttet sammen med veier. Det er $K$ veier i landet IOI, og hver vei forbinder $2$ ulike byer. Biler kan kjøre fritt i begge retninger på veiene, men det er ikke mulig å reise fra én by til en annen utenom veiene.

JOI-kun, som bor i by $1$ i landet IOI, har bestemt seg for å ta drosje til bestemoren sin, som bor i by $N$. I landet IOI finnes det $N$ drosjeselskaper, fra drosjeselskap $1$ til drosjeselskap $N$. Drosjeselskapene i landet IOI har følgende litt spesielle regler:

• En drosje fra drosjeselskap $i$ kan man bare sette seg inn i i by $i$.
• Taksten for en drosje fra drosjeselskap $i$ er $C_i$, uavhengig av hvor langt man kjører.
• En drosje fra drosjeselskap $i$ kan kjøre langs maksimalt $R_i$ sammenhengende veier etter at man har satt seg inn.

For eksempel, når $R_1 = 2$, kan man kjøre langs maksimalt $2$ veier dersom man tar en drosje fra drosjeselskap $1$ i by $1$. For å kjøre langs $3$ eller flere veier må man derfor bytte drosje i en by underveis.

JOI-kun kan ikke gå inn i eller ut av en drosje noe annet sted enn i en by. Han kan heller ikke bruke noe annet fremkomstmiddel enn drosje. Skriv et program som finner den minste totale taksten JOI-kun må betale for å komme seg til by $N$.

Inndata

Inndataene består av $1 + N + K$ linjer.

Den $1$. linjen inneholder $2$ heltall $N, K$ ($2 \le N \le 5000$, $N - 1 \le K \le 10000$) atskilt med mellomrom. Dette angir at landet IOI består av $N$ byer, og at antallet veier i landet IOI er $K$.

Den $i$-te linjen ($1 \le i \le N$) av de følgende $N$ linjene inneholder $2$ heltall $C_i, R_i$ ($1 \le C_i \le 10000$, $1 \le R_i \le N$) atskilt med mellomrom. Dette angir at taksten for en drosje fra drosjeselskap $i$ er $C_i$, og at den kan kjøre langs maksimalt $R_i$ sammenhengende veier etter påstigning.

Den $j$-te linjen ($1 \le j \le K$) av de følgende $K$ linjene inneholder $2$ ulike heltall $A_j, B_j$ ($1 \le A_j < B_j \le N$) atskilt med mellomrom. Dette angir at det går en vei mellom by $A_j$ og by $B_j$. Det samme paret $(A_j, B_j)$ forekommer ikke $2$ eller flere ganger.

I de oppgitte inndataene er det garantert at man kan komme seg fra enhver by til enhver annen by ved å bytte mellom drosjer.

Utdata

Skriv ut på $1$ linje et heltall som angir den minste totale taksten JOI-kun trenger for å reise fra by $1$ til by $N$.

Eksempler

Inndata 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

Forklaring

Eksemplet ovenfor tilsvarer figuren nedenfor. Sirkler representerer byer, og linjer representerer veier.

For at JOI-kun i dette eksemplet skal komme seg til by $6$ med lavest mulig takst, gjør han følgende:

• Tar drosje fra by $1$ til by $5$. (Takst $400$)
• Tar drosje fra by $5$ til by $6$. (Takst $300$)

Siden den totale taksten når JOI-kun følger denne ruten er $400 + 300 = 700$, skriver vi ut $700$.