IOI 国由从町 $1$ 到町 $N$ 的 $N$ 座城镇组成，城镇与城镇之间由道路连接。IOI 国有 $K$ 条道路，每条道路连接 $2$ 座不同的城镇。汽车可以在道路上双向自由通行，但不能通过道路以外的地方从一座城镇前往另一座城镇。

住在 IOI 国町 $1$ 的 JOI 君决定乘坐出租车前往住在町 $N$ 的祖母家。IOI 国有从出租车公司 $1$ 到出租车公司 $N$ 的 $N$ 家出租车公司。IOI 国的出租车公司有以下略微特殊的规定：

• 出租车公司 $i$ 的出租车只能在町 $i$ 乘车。
• 出租车公司 $i$ 的出租车车费无论行驶距离远近均为 $C_i$。
• 出租车公司 $i$ 的出租车自乘车起最多只能连续经过 $R_i$ 条道路。

例如当 $R_1 = 2$ 时，如果从町 $1$ 乘坐出租车公司 $1$ 的出租车，最多只能经过 $2$ 条道路，因此若要经过 $3$ 条或以上的道路，就需要在途中的城镇换乘出租车。

JOI 君不能在城镇以外的地点上下出租车，也不能使用出租车以外的交通工具。请编写一个程序，求出 JOI 君到达町 $N$ 所需的总车费的最小值。

输入格式

输入共 $1 + N + K$ 行。

第 $1$ 行包含 $2$ 个以空格分隔的整数 $N, K$（$2 \le N \le 5000$，$N - 1 \le K \le 10000$），表示 IOI 国由 $N$ 座城镇组成，且 IOI 国的道路条数为 $K$。

接下来 $N$ 行中的第 $i$ 行（$1 \le i \le N$）包含 $2$ 个以空格分隔的整数 $C_i, R_i$（$1 \le C_i \le 10000$，$1 \le R_i \le N$），表示出租车公司 $i$ 的出租车车费为 $C_i$，且自乘车起最多只能连续经过 $R_i$ 条道路。

接下来 $K$ 行中的第 $j$ 行（$1 \le j \le K$）包含 $2$ 个不同的以空格分隔的整数 $A_j, B_j$（$1 \le A_j < B_j \le N$），表示町 $A_j$ 与町 $B_j$ 之间存在一条道路。相同的 $(A_j, B_j)$ 组合不会出现 $2$ 次或以上。

在给定的输入数据中，保证从任意一座城镇都可以通过换乘出租车前往任意另一座城镇。

输出格式

输出 $1$ 行一个整数，表示 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

说明

上述样例对应下图。圆圈表示城镇，线段表示道路。

在此样例中，JOI 君要以最小车费到达町 $6$，可按如下方式出行：

• 从町 $1$ 乘坐出租车前往町 $5$。（车费 $400$）
• 从町 $5$ 乘坐出租车前往町 $6$。（车费 $300$）

JOI 君走这条路线时的总车费为 $400 + 300 = 700$，因此输出 $700$。