전화

농부 존의 소 $N$마리가 일렬로 서 있다. 소들은 $1 \ldots N$의 번호가 붙어 있다 ($1\le N\le 5\cdot 10^4$). $i$번째 소의 품종 번호는 $b_i$이며 $1 \ldots K$ 범위에 있다 ($1\le K\le 50$). 소들은 $1$번 소에서 $N$번 소로 메시지를 전달하는 최선의 방법을 찾으려고 한다.

$i$번 소에서 $j$번 소로 메시지를 전달하는 데는 $|i-j|$의 시간이 걸린다. 하지만 모든 품종이 서로 통신하려는 것은 아니며, 이는 $K \times K$ 행렬 $S$로 주어진다. $S_{ij} = 1$이면 품종 $i$의 소가 품종 $j$의 소에게 메시지를 전달하려 하고, $0$이면 그렇지 않다. $S_{ij}=S_{ji}$라는 보장은 없으며, 같은 품종끼리 통신하지 않으려는 경우 $S_{ii} = 0$일 수도 있다.

메시지를 전달하는 데 필요한 최소 시간을 구하라.

첫째 줄에 $N$과 $K$가 주어진다.

둘째 줄에 $N$개의 정수 $b_1,b_2,\ldots,b_N$이 공백으로 구분되어 주어진다.

다음 $K$개의 줄은 행렬 $S$를 나타낸다. 각 줄은 $K$비트 문자열이며, $S_{ij}$는 위에서 $i$번째 문자열의 $j$번째 비트이다.

필요한 최소 시간을 정수 하나로 출력한다. $1$번 소에서 $N$번 소로 메시지를 전달할 수 없으면 $-1$을 출력한다.