Country SS consists of N towns indexed from 1 to N, and each town i has its own inter city bus (IC Bus for short) system i. There is K roads between towns, each road connects two di?erent towns. The bus can move freely in both directions on the road.

Quang is living in the town 1 in the country, and decided to go to the grandmother's house in the town N by some inter city buses. There are some special rules in this country:

? If the passenger want to use the IC Bus of the town i, he has to only ride at the town i.

? The bus fares of the IC Bus system i is Ci regardless of the distance that the passenger used.

? The IC Bus system i allows to pass maximum Di towns per trip. If the trip has to pass more than Di towns, the passenger has to change to another IC Bus system.

? The passenger will not be able ride to or down from the bus at a middle point di?erent than the town.

Your task is to to ?nd the minimum value of the sum of the fare needed for Quang to reach the town N from the town 1.

Input

The input consists of 1 + N + K lines.

The ?rst line contains two positive integers N and K (2 = < N = < 5000; N - 1 = < K = < 10000).

i-th line in the N following lines contains 2 positive integers Ci and Di (1 = < Ci = < 10000; 1 = < Di = < N) which are the taxi fare and the maximum number of passing towns of the IC Bus system i.

Each line in the K following lines contains two positive integers i and j (1 = < i < j = < N) which means these two towns has a direct road connecting them.

Output

You should output on a single line an unique integer that is the minimum value of the sum of the fare necessary for Quang to go to the town N from the town 1.

Examples

Input

6 6

400 2

200 1

500 3

900 1

400 4

200 5

1 2

1 5

2 3

2 4

3 6

4 6

Output

800