問題文

$N$ 頂点 $M$ 辺からなる有向グラフ $G$ が与えられます．頂点には $1, 2, \\ldots, N$ の番号がついています．$i$ 番目の辺は $a_i$ から $b_i$ に向かう有向辺で，$a_i < b_i$ が成り立っています．

正整数列 $W = (W_1, W_2, \\ldots, W_N)$ の美しさを，次が成り立つような正整数 $x$ の最大値として定義します．

• $G$ における頂点 $1$ から頂点 $N$ への任意のパス $(v_1, \\ldots, v_k)$ ($v_1 = 1, v_k = N$) に対し，$\\sum_{i=1}^k W_{v_i}$ は $x$ の倍数である．

整数列 $A = (A_1, A_2, \\ldots, A_N)$ が与えられます．正整数列 $W = (W_1, \\ldots, W_N)$ を，$A_i \\neq -1 \\implies W_i = A_i$ を満たすように定めるとき，その美しさとしてありうる最大値を求めてください．ただし，最大値が存在しない場合には -1 を出力してください．

制約

• $2\\leq N\\leq 3\\times 10^5$
• $1\\leq M\\leq 3\\times 10^5$
• $1\\leq a_i < b_i \\leq N$
• $i\\neq j$ ならば $(a_i,b_i)\\neq (a_j,b_j)$
• 与えられるグラフ $G$ において，頂点 $1$ から頂点 $N$ へのパスが存在する．
• $A_i = -1$ または $1\\leq A_i\\leq 10^{12}$

入力

入力は以下の形式で標準入力から与えられます．

$N$ $M$ $a_1$ $b_1$ $\\vdots$ $a_M$ $b_M$ $A_1$ $A_2$ $\\ldots$ $A_N$

出力

正整数列 $W$ の美しさとしてありうる最大値を出力してください．ただし，最大値が存在しない場合には -1 を出力してください．

入力例 1

4 4
1 2
1 3
2 4
3 4
-1 3 7 -1

出力例 1

4

頂点 $1$ から頂点 $N$ へのパスは，$(1,2,4)$, $(1,3,4)$ の $2$ 個です． 例えば $W = (5, 3, 7, 8)$ の美しさは $4$ となります．実際，$W_1 + W_2 + W_4 = 16$, $W_1 + W_3 + W_4 = 20$ はともに $4$ の倍数です．

入力例 2

4 5
1 2
1 3
2 4
3 4
1 4
-1 3 7 -1

出力例 2

1

頂点 $1$ から頂点 $N$ へのパスは，$(1,2,4)$, $(1,3,4)$, $(1,4)$ の $3$ 個です． 例えば $W = (5, 3, 7, 8)$ の美しさは $1$ となります．

入力例 3

4 4
1 2
1 3
2 4
3 4
3 -1 -1 7

出力例 3

-1

例えば $W = (3, 10^{100}, 10^{100}, 7)$ の美しさは $10^{100}+10$ となります．$W$ の美しさをいくらでも大きくできるため，その最大値は存在しません．

入力例 4

5 5
1 3
3 5
2 3
3 4
1 4
2 -1 3 -1 4

出力例 4

9