Landið IOI samanstendur af $N$ bæjum, frá bæ $1$ til bæjar $N$, og bæirnir eru tengdir saman með vegum. Í landinu IOI eru $K$ vegir og hver vegur tengir saman $2$ ólíka bæi. Bílar geta ekið frjálslega í báðar áttir eftir vegunum, en ekki er hægt að komast frá einum bæ til annars utan vega.

JOI-kun, sem býr í bæ $1$ í landinu IOI, ákvað að fara með leigubíl heim til ömmu sinnar sem býr í bæ $N$. Í landinu IOI eru $N$ leigubílafyrirtæki, frá leigubílafyrirtæki $1$ til leigubílafyrirtækis $N$. Leigubílafyrirtækin í landinu IOI hafa eftirfarandi nokkuð sérstakar reglur:

• Aðeins er hægt að stíga upp í leigubíl frá leigubílafyrirtæki $i$ í bæ $i$.
• Fargjaldið í leigubíl frá leigubílafyrirtæki $i$ er $C_i$, óháð vegalengdinni sem farin er.
• Leigubíll frá leigubílafyrirtæki $i$ getur ekið eftir í mesta lagi $R_i$ vegum í röð eftir að stigið er upp í hann.

Til dæmis, þegar $R_1 = 2$, ef stigið er upp í leigubíl frá leigubílafyrirtæki $1$ í bæ $1$, er aðeins hægt að aka eftir í mesta lagi $2$ vegum, þannig að til að aka eftir $3$ eða fleiri vegum þarf að skipta um leigubíl í einhverjum bæ á leiðinni.

JOI-kun getur hvorki stigið upp í né farið út úr leigubíl á neinum öðrum stað en í bæ. Hann getur heldur ekki notað neinn annan ferðamáta en leigubíla. Skrifið forrit til að finna lágmarks heildarfargjald sem JOI-kun þarf að greiða til að komast til bæjar $N$.

Inntak

Inntakið samanstendur af $1 + N + K$ línum.

Í $1$. línunni eru $2$ heiltölur $N, K$ ($2 \le N \le 5000$, $N - 1 \le K \le 10000$) aðskildar með bili. Þetta gefur til kynna að landið IOI samanstandi af $N$ bæjum og að fjöldi vega í landinu IOI sé $K$.

Í $i$-tu línunni ($1 \le i \le N$) af næstu $N$ línum eru $2$ heiltölur $C_i, R_i$ ($1 \le C_i \le 10000$, $1 \le R_i \le N$) aðskildar með bili. Þetta gefur til kynna að fargjald leigubíls frá leigubílafyrirtæki $i$ sé $C_i$ og að hann geti ekið eftir í mesta lagi $R_i$ vegum í röð eftir að stigið er upp í hann.

Í $j$-tu línunni ($1 \le j \le K$) af næstu $K$ línum eru $2$ ólíkar heiltölur $A_j, B_j$ ($1 \le A_j < B_j \le N$) aðskildar með bili. Þetta gefur til kynna að vegur liggi á milli bæjar $A_j$ og bæjar $B_j$. Sama parið $(A_j, B_j)$ kemur ekki fyrir $2$ sinnum eða oftar.

Í gefnum inntaksgögnum er tryggt að hægt sé að komast frá hvaða bæ sem er til hvaða annars bæjar sem er með því að skipta á milli leigubíla.

Úttak

Skrifið út í $1$ línu heiltölu sem táknar lágmarks heildarfargjald sem JOI-kun þarf til að fara frá bæ $1$ til bæjar $N$.

Dæmi

Inntak 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

Úttak 1

700

Athugasemd

Dæmið hér að ofan samsvarar myndinni hér að neðan. Hringir tákna bæi og línur tákna vegi.

Til þess að JOI-kun komist til bæjar $6$ í þessu dæmi með lágmarksfargjaldi fer hann svona að:

• Tekur leigubíl frá bæ $1$ og fer til bæjar $5$. (Fargjald $400$)
• Tekur leigubíl frá bæ $5$ og fer til bæjar $6$. (Fargjald $300$)

Þar sem heildarfargjaldið þegar JOI-kun fer þessa leið er $400 + 300 = 700$, er skrifað út $700$.