Taxis

In a country with $N$ towns and $K$ roads, taxi company $i$ charges $C_i$ and may traverse at most $R_i$ consecutive roads per ride, boarding only at town $i$. Find the minimum total fare from town 1 to town $N$.

Line 1: $N$, $K$. Next $N$ lines: $C_i$, $R_i$. Next $K$ lines: roads.

Print the minimum total fare.