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$。