택시

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

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

최소 총 요금을 출력한다.