The country of IOI consists of $N$ towns numbered from town $1$ to town $N$, and the towns are connected by roads. There are $K$ roads in the country of IOI, and every road connects $2$ distinct towns. Cars can move freely in both directions along the roads, but one cannot go from one town to another without using roads.

JOI-kun, who lives in town $1$ of the country of IOI, decided to take taxis to his grandmother's house in town $N$. In the country of IOI, there are $N$ taxi companies numbered from taxi company $1$ to taxi company $N$. The taxi companies in the country of IOI have the following somewhat special rules:

• A taxi of taxi company $i$ can only be boarded in town $i$.
• The fare of a taxi of taxi company $i$ is $C_i$, regardless of the distance traveled.
• A taxi of taxi company $i$ can traverse at most $R_i$ consecutive roads after being boarded.

For example, when $R_1 = 2$, if JOI-kun boards a taxi of taxi company $1$ from town $1$, he can traverse at most $2$ roads, so in order to traverse $3$ or more roads, he needs to transfer to another taxi at an intermediate town.

JOI-kun cannot board or get off a taxi at any point other than a town. Also, he cannot use any means of transportation other than taxis. Write a program to find the minimum total fare required for JOI-kun to reach town $N$.

Input

The input consists of $1 + N + K$ lines.

The $1$-st line contains $2$ space-separated integers $N, K$ ($2 \le N \le 5000$, $N - 1 \le K \le 10000$). This indicates that the country of IOI consists of $N$ towns and that the number of roads in the country of IOI is $K$.

The $i$-th line ($1 \le i \le N$) of the following $N$ lines contains $2$ space-separated integers $C_i, R_i$ ($1 \le C_i \le 10000$, $1 \le R_i \le N$). This indicates that the fare of a taxi of taxi company $i$ is $C_i$, and it can traverse at most $R_i$ consecutive roads after being boarded.

The $j$-th line ($1 \le j \le K$) of the following $K$ lines contains $2$ distinct space-separated integers $A_j, B_j$ ($1 \le A_j < B_j \le N$). This indicates that there is a road between town $A_j$ and town $B_j$. The same pair $(A_j, B_j)$ does not appear $2$ or more times.

In the given input data, it is guaranteed that it is possible to travel from any town to any other town by transferring between taxis.

Output

Output an integer representing the minimum total fare required for JOI-kun to go from town $1$ to town $N$, in $1$ line.

Examples

Input 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

Output 1

700

Note

The example above corresponds to the following figure. Circles represent towns, and lines represent roads.

In this example, for JOI-kun to reach town $6$ with the minimum fare, he proceeds as follows:

• Take a taxi from town $1$ and go to town $5$. (Fare $400$)
• Take a taxi from town $5$ and go to town $6$. (Fare $300$)

Since the total fare when JOI-kun takes such a route is $400 + 300 = 700$, output $700$.