IOI елі $1$-қалашықтан $N$-қалашыққа дейінгі $N$ қалашықтан тұрады, ал қалашықтар бір-бірімен жолдар арқылы байланысқан. IOI елінде $K$ жол бар және әрбір жол әртүрлі $2$ қалашықты қосады. Көліктер жолдармен екі бағытта да еркін жүре алады, бірақ жолдан тыс жермен бір қалашықтан екінші қалашыққа бару мүмкін емес.

IOI елінің $1$-қалашығында тұратын JOI-кун $N$-қалашықта тұратын әжесінің үйіне таксимен баруды ұйғарды. IOI елінде $1$-такси компаниясынан $N$-такси компаниясына дейін $N$ такси компаниясы бар. IOI елінің такси компанияларында мынадай біршама ерекше ережелер бар:

• $i$-такси компаниясының таксиіне тек $i$-қалашықта ғана отыруға болады.
• $i$-такси компаниясы таксиінің жол ақысы жүріп өткен қашықтыққа қарамастан $C_i$-ге тең.
• $i$-такси компаниясының таксиі отырғаннан кейін қатарынан ең көп дегенде $R_i$ жолмен ғана жүріп өте алады.

Мысалы, $R_1 = 2$ болған жағдайда, $1$-қалашықтан $1$-такси компаниясының таксиіне отырса, ең көп дегенде $2$ жолмен ғана жүріп өтуге болады, сондықтан $3$ немесе одан да көп жолмен жүріп өту үшін жол-жөнекей қалашықта басқа таксиге ауысып міну қажет.

JOI-кун қалашықтан басқа жерде таксиге отыра да, таксиден түсе де алмайды. Сондай-ақ ол таксиден басқа қатынас құралдарын пайдалана алмайды. JOI-кунға $N$-қалашыққа жету үшін қажетті жол ақыларының қосындысының ең кіші мәнін табатын программа жазыңыз.

Енгізу деректері

Енгізу деректері $1 + N + K$ жолдан тұрады.

$1$-ші жолда бос орын арқылы бөлінген $2$ бүтін сан $N, K$ ($2 \le N \le 5000$, $N - 1 \le K \le 10000$) жазылған. Бұл IOI елінің $N$ қалашықтан тұратынын және IOI еліндегі жолдар саны $K$ екенін білдіреді.

Келесі $N$ жолдың $i$-ші жолында ($1 \le i \le N$) бос орын арқылы бөлінген $2$ бүтін сан $C_i, R_i$ ($1 \le C_i \le 10000$, $1 \le R_i \le N$) жазылған. Бұл $i$-такси компаниясы таксиінің жол ақысы $C_i$ екенін және отырғаннан кейін қатарынан ең көп дегенде $R_i$ жолмен ғана жүріп өте алатынын білдіреді.

Келесі $K$ жолдың $j$-ші жолында ($1 \le j \le K$) бос орын арқылы бөлінген әртүрлі $2$ бүтін сан $A_j, B_j$ ($1 \le A_j < B_j \le N$) жазылған. Бұл $A_j$ қалашығы мен $B_j$ қалашығының арасында жол бар екенін білдіреді. Бірдей $(A_j, B_j)$ жұбы $2$ немесе одан да көп рет кездеспейді.

Берілген енгізу деректерінде кез келген қалашықтан кез келген басқа қалашыққа такси ауыстырып міну арқылы жетуге болатынына кепілдік беріледі.

Шығару деректері

JOI-кунға $1$-қалашықтан $N$-қалашыққа дейін бару үшін қажетті жол ақыларының қосындысының ең кіші мәнін білдіретін бүтін санды $1$ жолда шығарыңыз.

Мысалдар

Енгізу 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

Шығару 1

700

Ескертпе

Жоғарыдағы мысал төмендегі суретке сәйкес келеді. Шеңберлер қалашықтарды, ал сызықтар жолдарды білдіреді.

Бұл мысалда JOI-кун ең аз жол ақысымен $6$-қалашыққа жету үшін келесідей әрекет етеді:

• $1$-қалашықтан таксиге отырып, $5$-қалашыққа барады. (Жол ақысы $400$)
• $5$-қалашықтан таксиге отырып, $6$-қалашыққа барады. (Жол ақысы $300$)

JOI-кун осындай маршрутпен жүргендегі жол ақыларының қосындысы $400 + 300 = 700$ болғандықтан, $700$ санын шығарамыз.