Telephone

문제

Farmer John's $NN$ cows, conveniently numbered $1\dots N1\; \backslash ldots\; N$, are standing in a line ($1\le N\le 5\cdot {10}^{4}1\backslash le\; N\backslash le\; 5\backslash cdot\; 10^4$). The $ii$th cow has a breed identifier $b_{i}b\_i$ in the range $1\dots K1\; \backslash ldots\; K$, with $1\le K\le 501\backslash le\; K\backslash le\; 50$. The cows need your help to figure out how to best transmit a message from cow $11$ to cow $NN$.

It takes $\mathrm{\mid }i-j\mathrm{\mid }|i-j|$ time to transmit a message from cow $ii$ to cow $jj$. However, not all breeds are willing to communicate with each other, as described by a $K\times KK\; \backslash times\; K$ matrix $SS$, where $S_{ij}=1S\_\{ij\}\; =\; 1$ if a cow of breed $ii$ is willing to transmit a message to a cow of breed $jj$, and $00$ otherwise. It is not necessarily true that $S_{ij}=S_{ji}S\_\{ij\}=S\_\{ji\}$, and it may even be the case that $S_{ii}=0S\_\{ii\}\; =\; 0$ if cows of breed $ii$ are unwilling to communicate with each-other.

Please determine the minimum amount of time needed to transmit the message.

입력

The first line contains $NN$ and $KK$.

The next line contains $NN$ space-separated integers $b_1,b_2,\dots ,b_{N}b\_1,b\_2,\backslash ldots,b\_N$.

The next $KK$ lines describe the matrix $SS$. Each consists of a string of $KK$ bits, $S_{ij}S\_\{ij\}$ being the $jj$th bit of the $ii$th string from the top.

출력

Print a single integer giving the minimum amount of time needed. If it is impossible to transmit the message from cow $11$ to cow $NN$, then output $-1-1$.

5 4
1 4 2 3 4
1010
0001
0110
0100

6