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