Description

Farmer John has $N$ cows, numbered $1 \ldots N$, standing in a line ($1 \le N \le 5 \cdot 10^4$). The breed ID of cow $i$ is $b_i$, in the range $1 \ldots K$, where $1 \le K \le 50$. The cows need your help to find the best way to transmit a message from cow $1$ to cow $N$.

Transmitting a message from cow $i$ to cow $j$ takes time $|i-j|$. However, not all breeds of cows are willing to talk to each other, as described by a $K \times K$ matrix $S$. If a cow of breed $i$ is willing to transmit a message to a cow of breed $j$, then $S_{ij}=1$, otherwise it is $0$. It is not guaranteed that $S_{ij}=S_{ji}$, and it is possible that $S_{ii}=0$ if cows of breed $i$ are not willing to communicate with each other.

Find the minimum time required to transmit the message.

Input Format

The first line contains $N$ and $K$.

The next line contains $N$ space-separated integers $b_1,b_2,\dots,b_N$.

The following $K$ lines describe the matrix $S$. Each line contains a string of $K$ binary digits. For the $i$-th string from top to bottom, its $j$-th character is $S_{ij}$.

Output Format

Output one integer, the minimum time required. If it is impossible to transmit the message from cow $1$ to cow $N$, output $-1$.

5 4
1 4 2 3 4
1010
0001
0110
0100

6

Hint

The optimal transmission sequence is $1 \to 4 \to 3 \to 5$. The total time is $|1-4|+|4-3|+|3-5|=6$.

Test Point Properties:

• Test points 1-5 satisfy $N \le 1000$.
• Test points 6-13 have no additional constraints.

Problem provided by: Dhruv Rohatgi

Translated by ChatGPT 5