Time Limit: 5s
Memory Limit: 256MB
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:
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.
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.
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.
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
800
Quang uses the IC Bus of the town 1 and then of the town 5.