Problem Statement

You are given a directed graph $G$ with $N$ vertices and $M$ edges. The vertices are numbered $1, 2, \ldots, N$. The $i$-th edge is directed from Vertex $a_i$ to Vertex $b_i$, where $a_i < b_i$.

The beautifulness of a sequence of positive integers $W = (W_1, W_2, \ldots, W_N)$ is defined as the maximum positive integer $x$ that satisfies the following:

• For every path $(v_1, \ldots, v_k)$ ($v_1 = 1, v_k = N$) from Vertex $1$ to Vertex $N$ in $G$, $\sum_{i=1}^k W_{v_i}$ is a multiple of $x$.

You are given an integer sequence $A = (A_1, A_2, \ldots, A_N)$. Find the maximum beautifulness of a sequence of positive integers $W = (W_1, \ldots, W_N)$ such that $A_i \neq -1 \implies W_i = A_i$. If the maximum beautifulness does not exist, print -1.

Constraints

• $2\leq N\leq 3\times 10^5$
• $1\leq M\leq 3\times 10^5$
• $1\leq a_i < b_i \leq N$
• $(a_i,b_i)\neq (a_j,b_j)$ if $i\neq j$
• In the given graph $G$, there is a path from Vertex $1$ to Vertex $N$.
• $A_i = -1$ or $1\leq A_i\leq 10^{12}$

Input

Input is given from Standard Input in the following format:

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

Output

Print the maximum beautifulness of a sequence of positive integers $W$. If the maximum beautifulness does not exist, print -1.