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

以下图例说明输入输出。图中圆圈代表城镇，线段代表道路。 

在此示例中，JOI 君以最低费用到达城镇 $6$ 的方法是：

• 从城镇 $1$ 乘出租车到城镇 $5$，费用 $400$。
• 之后从城镇 $5$ 乘出租车到达城镇 $6$，费用 $300$。

总费用为 $400 + 300 = 700$，因此应输出 $700$。

本翻译由 AI 自动生成