택시

문제

IOI 국은 마을 1부터 마을 N까지 N개의 마을로 이루어져 있고, 마을과 마을은 도로로 연결되어 있다. IOI 국에는 K개의 도로가 있으며, 모든 도로는 서로 다른 2개의 마을을 연결한다. 자동차는 도로를 양방향으로 자유롭게 이동할 수 있지만, 도로 이외의 곳을 지나 어떤 마을에서 다른 마을로 갈 수는 없다.

IOI 국의 마을 1에 사는 JOI 군은, 마을 N에 사는 할머니 댁까지 택시로 가기로 했다. IOI 국에는 택시 회사 1부터 택시 회사 N까지 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 ≦ N ≦ 5000, N - 1 ≦ K ≦ 10000) 가 공백으로 구분되어 쓰여 있다. 이는 IOI 국이 N개의 마을로 이루어져 있고, IOI 국의 도로의 개수가 K개임을 나타낸다.

이어지는 N개의 줄 중 i번째 줄 (1 ≦ i ≦ N) 에는 2개의 정수 $C_{i}$, $R_{i}$ (1 ≦ $C_{i}$ ≦ 10000, 1 ≦ $R_{i}$ ≦ N) 가 공백으로 구분되어 쓰여 있다. 이는 택시 회사 i의 택시의 요금이 $C_{i}$ 이고, 탑승한 후 연속해서 최대 $R_{i}$ 개의 도로만 지날 수 있음을 나타낸다.

이어지는 K개의 줄 중 j번째 줄 (1 ≦ j ≦ K) 에는 서로 다른 2개의 정수 $A_{j}$, $B_{j}$ (1 ≦ $A_{j}$ ＜ $B_{j}$ ≦ N) 가 공백으로 구분되어 쓰여 있다. 이는 마을 $A_{j}$ 와 마을 $B_{j}$ 사이에 도로가 존재함을 나타낸다. 같은 ($A_{j}$, $B_{j}$) 의 쌍이 2번 이상 쓰여 있는 경우는 없다.

주어지는 입력 데이터에서는 어느 마을에서 다른 어느 마을로도 택시를 갈아타며 갈 수 있음이 보장된다.

출력

JOI 군이 마을 1에서 마을 N까지 가는 데 필요한 요금 합계의 최솟값을 나타내는 정수를 1개의 줄에 출력한다.

예제 입력 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

위의 예제는 아래 그림에 대응한다. 원은 마을을, 선은 도로를 나타낸다.

이 예제에서 JOI 군이 최소의 요금으로 마을 6에 도달하려면 다음과 같이 하면 된다.

• 마을 1에서 택시를 타고 마을 5로 간다. (요금 400)
• 마을 5에서 택시를 타고 마을 6으로 간다. (요금 300)

JOI 군이 이러한 경로를 지난 경우의 요금 합계는 400 + 300 = 700 이므로, 700을 출력한다.