AT_joi2014yo_e タクシー (Taxis)

IOI 国由编号为 $1$ 到 $N$ 的 $N$ 个城镇组成，这些城镇通过道路连接在一起。国中有 $K$ 条道路，每条道路连接两个不同的城镇。车辆可以在道路上双向自由行驶，但不能通过除道路以外的方式来往于城镇之间。 住在城镇 $1$ 的 JOI 君决定乘坐出租车前往位于城镇 $N$ 的祖母家。IOI 国有 $N$ 个出租车公司，编号从 $1$ 到 $N$。每个出租车公司在不同的地方有自己的特殊规则： - 出租车公司 $i$ 的车只能在城镇 $i$ 乘坐。 - 出租车公司 $i$ 的费用是固定的，为 $C_i$，与行驶的距离无关。 - 出租车公司 $i$ 的车在一次行程中最多只能走过 $R_i$ 条道路，超过这个数就需要换乘。 比如，若 $R_1 = 2$，则乘坐出租车公司 $1$ 的车从城镇 $1$ 出发时，最多只能经过 $2$ 条道路。要想经过更多的道路，JOI 君必须在途中换乘其他公司的出租车。 JOI 君不能在城镇以外的地点上下出租车，也不能使用其他交通方式。请帮助 JOI 君计算从城镇 $1$ 到达城镇 $N$ 所需的最低费用。

输入包括 $1 + N + K$ 行信息。 第 $1$ 行提供两个整数 $N$ 和 $K$，分别表示城镇数量和道路数量，其中 $2 \leq N \leq 5000$，$N - 1 \leq K \leq 10000$。 接下来的 $N$ 行中，第 $i$ 行提供两个整数 $C_i, R_i$，表示出租车公司 $i$ 的费用为 $C_i$，并且每次最多可以连续行驶 $R_i$ 条路。$1 \leq C_i \leq 10000$，$1 \leq R_i \leq N$。 接下来的 $K$ 行中，第 $j$ 行提供两个整数 $A_j, B_j$，代表城镇 $A_j$ 和城镇 $B_j$ 之间存在一条道路。$1 \leq A_j < B_j \leq N$。所有的道路互不重复。 输入保证从任意城镇出发都能通过换乘到达任意其他城镇。

输出为一个整数，表示 JOI 君从城镇 $1$ 到城镇 $N$ 的最小总费用。 ### 示例解释 1 以下图例说明输入输出。图中圆圈代表城镇，线段代表道路。 !\[2014-yo-t5-fig01.png\](https://img.atcoder.jp/joi2014yo/2014-yo-t5-fig01.png) 在此示例中，JOI 君以最低费用到达城镇 $6$ 的方法是： - 从城镇 $1$ 乘出租车到城镇 $5$，费用 $400$。 - 之后从城镇 $5$ 乘出租车到达城镇 $6$，费用 $300$。 总费用为 $400 + 300 = 700$，因此应输出 $700$。 **本翻译由 AI 自动生成**

### Sample Explanation 1 上の入出力例は，以下の図に対応している．円は町を，線は道路を表す． !\[2014-yo-t5-fig01.png\](https://img.atcoder.jp/joi2014yo/2014-yo-t5-fig01.png) この入出力例で JOI 君が最小の運賃で町 $ 6 $ に到達するには，以下のようにする． 町 $ 1 $ からタクシーに乗って町 $ 5 $ に行く．(運賃 $ 400 $) 町 $ 5 $ からタクシーに乗って町 $ 6 $ に行く．(運賃 $ 300 $) JOI 君がこのようなルートを通った場合の運賃の合計は $ 400\ +\ 300\ =\ 700 $ であるので，$ 700 $ を出力する．