Країна IOI складається з $N$ містечок, пронумерованих від містечка $1$ до містечка $N$, які з'єднані між собою дорогами. У країні IOI є $K$ доріг, і кожна дорога з'єднує $2$ різних містечка. Автомобілі можуть вільно рухатися дорогами в обох напрямках, але потрапити з одного містечка до іншого поза дорогами неможливо.

JOI-кун, який живе в містечку $1$ країни IOI, вирішив поїхати на таксі до будинку своєї бабусі, яка живе в містечку $N$. У країні IOI є $N$ компаній таксі — від компанії таксі $1$ до компанії таксі $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$.

В $i$-му рядку ($1 \le i \le N$) із наступних $N$ рядків через пробіл записано $2$ цілі числа $C_i, R_i$ ($1 \le C_i \le 10000$, $1 \le R_i \le N$). Це означає, що вартість проїзду на таксі компанії $i$ дорівнює $C_i$, а після посадки воно може проїхати поспіль максимум $R_i$ доріг.

У $j$-му рядку ($1 \le j \le K$) із наступних $K$ рядків через пробіл записано $2$ різних цілі числа $A_j, B_j$ ($1 \le A_j < B_j \le N$). Це означає, що між містечком $A_j$ і містечком $B_j$ існує дорога. Одна й та сама пара $(A_j, B_j)$ не трапляється $2$ або більше разів.

У заданих вхідних даних гарантується, що з будь-якого містечка можна дістатися до будь-якого іншого містечка, пересідаючи з одного таксі на інше.

Вихідні дані

Виведіть в $1$ рядку ціле число — мінімальну загальну вартість проїзду, необхідну JOI-куну, щоб дістатися з містечка $1$ до містечка $N$.

Приклади

Вхідні дані 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

Примітка

Наведений вище приклад відповідає наступному рисунку. Кружечки позначають містечка, а лінії — дороги.

Щоб у цьому прикладі дістатися до містечка $6$ з мінімальною вартістю, JOI-кун діє таким чином:

• Сідає в таксі в містечку $1$ і їде до містечка $5$. (Вартість $400$)
• Сідає в таксі в містечку $5$ і їде до містечка $6$. (Вартість $300$)

Оскільки загальна вартість проїзду за таким маршрутом дорівнює $400 + 300 = 700$, слід вивести $700$.