#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e6+100;
const int M=1e7;
int n,k;
int head[N],cnt;
char c[105][105];
int b[N];
int dis[N];
struct edge
{
	int from;
	int to;
	int nex;
	int len;
}e[M];
void add(int x,int y,int z)
{
	e[++cnt]=(edge)
	{
		x,y,head[x],z
	};
	head[x]=cnt;
}
int vis[N];
queue<int>q;
void spfa()
{
	q.push(1);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=e[i].nex)
		{
			int v=e[i].to;
			if(dis[v]>dis[u]+e[i].len)
			{
				dis[v]=dis[u]+e[i].len;
     			if(vis[v]) continue;
				vis[v]=1;
				q.push(v);
			}
		}
	}
}
signed main()
{
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;i++) scanf("%lld",&b[i]);
	for(int i=1;i<=k;i++)
	for(int j=1;j<=k;j++) cin>>c[i][j];
	for(int i=2;i<=k+1;i++)
	{
		for(int j=1;j<=n-1;j++)
		{
			add(j+(i-1)*n,(j+1)+(i-1)*n,1);
			add((j+1)+(i-1)*n,j+(i-1)*n,1);
		}
	}
	for(int i=1;i<=n;i++) add(i,i+b[i]*n,0);
    for(int i=1;i<=k;i++)
    {
    	for(int j=1;j<=n;j++)
    	{
    		if(c[i][b[j]]=='1') add(j+i*n,j,0);
    	}
    }
    for(int i=1;i<=(k+1)*n;i++) dis[i]=1e18;
    dis[1]=0;
    vis[1]=1;
    spfa();
    if(dis[n]==1e18) cout<<-1;
    else cout<<dis[n];
	return 0;
}