1003 - InterCity Bus

Time Limit: 5s Memory Limit: 256MB

Submissions: 33 Solved: 6
Description

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 different 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 different than the town. 

Your task is to to find 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 first line contains two positive integers N and K (2 N 5000; N-1 K 10000). i-th line in the Nfollowing 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 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.

Sample 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
Sample Output
800
Hint

 Quang uses the IC Bus of the town 1 and then of the town 5.

 

 

Source