IOI 나라는 마을 \(1\)부터 마을 \(N\)까지 \(N\)개의 마을로 이루어져 있고, 마을과 마을은 도로로 이어져 있다. 도로는 \(K\)개이고, 모든 도로는 서로 다른 두 마을을 잇는다. 차는 도로를 양방향으로 자유롭게 다닐 수 있지만, 도로가 아니면 한 마을에서 다른 마을로 갈 수 없다. IOI 나라의 마을 \(1\)에 사는 JOI 군은 마을 \(N\)에 사는 할머니 댁까지 택시로 가기로 했다. IOI 나라에는 택시 회사 \(1\)부터 택시 회사 \(N\)까지 \(N\)개의 택시 회사가 있다. 이 나라의 택시 회사에는 조금 특이한 규칙이 있다. 택시 회사 \(i\)의 택시는 마을 \(i\)에서만 탈 수 있다. 택시 회사 \(i\)의 택시 요금은 이용한 거리와 관계없이 \(C_i\)이다. 택시 회사 \(i\)의 택시는 탄 뒤 연속해서 도로를 최대 \(R_i\)개만 지날 수 있다. 예를 들어 \(R_1 = 2\)이면, 마을 \(1\)에서 택시 회사 \(1\)의 택시를 타면 도로를 최대 \(2\)개만 지날 수 있으므로, 도로를 \(3\)개 이상 지나려면 중간 마을에서 택시를 갈아타야 한다. JOI 군은 마을이 아닌 곳에서 택시를 타거나 내릴 수 없다. 택시 이외의 이동 수단도 쓸 수 없다. JOI 군이 마을 \(N\)에 도착하기 위해 필요한 요금 합의 최솟값을 구하는 프로그램을 작성하라. |
입력은 다음 형식으로 주어진다.
\(N\) \(K\)
\(C_1\) \(R_1\)
\(\vdots\)
\(C_N\) \(R_N\)
\(A_1\) \(B_1\)
\(\vdots\)
\(A_K\) \(B_K\)
- 입력은 \(1+N+K\)줄이다.
- 첫째 줄에 정수 \(N\), \(K\)가 공백 하나로 구분되어 주어진다. IOI 나라가 마을 \(N\)개로 이루어지고 도로가 \(K\)개임을 나타낸다.
- 이어지는 \(N\)줄 가운데 \(i\)번째 줄(\(1 \le i \le N\))에는 정수 \(C_i\), \(R_i\)가 공백 하나로 구분되어 주어진다. 택시 회사 \(i\)의 요금이 \(C_i\)이고, 탄 뒤 연속해서 도로를 최대 \(R_i\)개만 지날 수 있음을 나타낸다.
- 이어지는 \(K\)줄 가운데 \(j\)번째 줄(\(1 \le j \le K\))에는 서로 다른 정수 \(A_j\), \(B_j\)가 공백 하나로 구분되어 주어지고, 마을 \(A_j\)와 마을 \(B_j\) 사이에 도로가 있음을 나타낸다. 같은 \((A_j, B_j)\) 쌍이 두 번 이상 나오지 않는다.
- 어느 마을에서든 택시를 갈아타며 다른 어느 마을로든 갈 수 있음이 보장된다.
- \(2 \le N \le 5000\)
- \(N-1 \le K \le 10000\)
- \(1 \le C_i \le 10000\)
- \(1 \le R_i \le N\)
- \(1 \le A_j \lt B_j \le N\)
- 입력되는 값은 모두 정수이다.
다음 형식으로 출력한다.
첫째 줄에 JOI 군이 마을 \(1\)에서 마을 \(N\)까지 가는 데 필요한 요금 합의 최솟값을 출력한다.
마을 \(1\)에서 택시를 타고 마을 \(5\)로 간다(요금 \(400\)). 마을 \(5\)에서 택시를 타고 마을 \(6\)으로 간다(요금 \(300\)). 합은 \(400+300=700\)이다.