问题

IOI国由 $N$ 个城市组成，编号从城市 $1$ 到城市 $N$ ，城市之间通过道路相连。IOI国有 $K$ 条道路，每条道路连接两个不同的城市。车辆可以双向自由行驶在道路上，但不能通过非道路的地点从一个城市到达另一个城市。

JOI同学住在IOI国的城市 $1$ ，决定乘坐出租车去祖母的家，位于城市 $N$ 。IOI国有 $N$ 家出租车公司，分别编号从出租车公司 $1$ 到出租车公司 $N$ 。IOI国的出租车公司有一些特殊规则：

• 只能在出租车公司 $i$ 的出租车上乘车，其中 $i$ 是城市 $i$ 的编号。
• 出租车公司 $i$ 的车费固定为 $C_i$ ，不论乘车路程如何。
• 出租车公司 $i$ 的出租车在乘车后连续最多只能经过 $R_i$ 条道路。

例如，当 $R_1 = 2$ 时，如果乘坐城市 $1$ 的出租车，则最多只能经过 $2$ 条道路，因此如果需要经过 $3$ 条以上的道路，则需要在途中的城市换乘出租车。

JOI同学不能在城市以外的地点乘坐或下车出租车，也不能使用除出租车以外的交通方式。请编写一个程序，计算JOI同学到达城市 $N$ 所需的最小总车费。

输入

输入由 $1 + N + K$ 行组成。

第 $1$ 行包含两个整数 $N$ 和 $K$ （ $2 \leqq N \leqq 5,000$，$N - 1 \leqq K \leqq 10,000$），表示IOI国有 $N$ 个城市和 $K$ 条道路。

接下来的 $N$ 行中的第 $i$ 行（ $1 \leqq i \leqq N$）包含两个整数 $C_i$ 和 $R_i$ （ $1 \leqq C_i \leqq 10,000$，$1 \leqq R_i \leqq N$），表示第 $i$ 家出租车公司的车费为 $C_i$ ，乘车后连续最多经过 $R_i$ 条道路。

接下来的 $K$ 行中的第 $j$ 行（ $1 \leqq j \leqq K$）包含两个不同的整数 $A_j$ 和 $B_j$ （ $1 \leqq Aj < Bj \leqq N$），表示城市 $A_j$ 和城市 $B_j$ 之间存在一条道路。同一对 $(A_j, B_j)$ 不会出现两次以上。

在给定的输入数据中，保证从任意一个城市到另一个城市都可以通过乘坐出租车到达。

输出

输出一个整数，表示JOI同学从城市 $1$ 前往城市 $N$ 所需的最小总车费。

示例输入 1

6 6
400 2
200 1
600 3
1000 1
300 5
700 4
1 2
2 3
3 6
4 6
1 5
2 4

示例输出 1

700

上述输入输出示例对应以下图示。圆表示城市，线表示道路。

为了以最低的车费到达城市 $6$ ，JOI同学可以按照以下步骤进行：

从城市 $1$ 乘坐出租车去城市 $5$ （车费为 $400$ ）。
从城市 $5$ 乘坐出租车去城市 $6$ （车费为 $300$ ）。
如果JOI同学按照这种路径行驶，总车费为 $400 + 300 = 700$ ，因此输出为 $700$ 。