택시

시간 제한1초메모리 제한128 MB

요약

각 마을에서만 탈 수 있고 요금과 이동 가능한 도로 수가 정해진 택시를 갈아타며 1번 마을에서 N번 마을까지 최소 요금으로 이동합니다.

문제

$N$ 개 마을과 $K$ 개 도로로 이루어진 나라에서, 마을 $i$ 의 택시는 요금 $C_i$ 로 최대 $R_i$ 개의 연속 도로만 지날 수 있다. 마을 1에서 $N$ 까지 택시만 이용할 때 최소 총 요금을 구한다.

첫 줄에 $N$ , $K$ . 다음 $N$ 줄에 $C_i$ , $R_i$ . 다음 $K$ 줄에 도로 $(A_j, B_j)$ .

최소 총 요금을 출력한다.

예제 1

입력

예상 출력