#include <cstdio>
#include <iostream>
#include <queue>
#include <string>
#include <utility>
#include <vector>

using namespace std;

template <typename T>
void read (T& num) {
    T res = 0;
	T ch = getchar();
	T op = 1;

    while (!isdigit (ch) && ch != EOF) {
		op = (ch == '-' ? -1 : 1);
        ch = getchar ();
	}

    while (isdigit (ch)) {
        res = (res * 10) + (ch - '0');
        ch = getchar ();
    }
    num = op * res;
}

class Read {
	public:
	Read operator>> (auto& other) {
		read (other);
		return (*this);
	}
};

Read in;

constexpr int N = 51145;
constexpr int K = 55;

int n;
int k;
int b[N];
char strs[K][K];
vector<pair<int, int>> graph[N * K];
int dis[N * K];
bool flag[N * K];

inline int getPoint (int now, int type) {
	return (now - 1) * (k + 1) + type;
}

inline void add (int u, int v, int w) {
	graph[u].emplace_back(v, w);
}

int main () {
	
	freopen ("telephone.in", "r" ,stdin);
	freopen ("telephone.out", "w", stdout);

	in >> n >> k;
	for (int i = 1; i <= n; i++) {
		in >> b[i];
	}
	for (int i = 1; i <= k; i++) {
		for (int j = 1; j <= k; j++) {
			strs[i][j] = getchar ();
		}
		getchar ();
	}
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= k; j++) {
			if (strs[b[i]][j] == '1') {
				add (getPoint (i, 0), getPoint (i, j), 0);
			}
		}
		add (getPoint (i, b[i]), getPoint (i, 0), 0);

		if (i > 1) {
			for (int j = 1; j <= k; j++) {
				add (getPoint (i - 1, j), getPoint (i, j), 1);
				add (getPoint (i, j), getPoint (i - 1, j), 1);
			}
		}
	}

	fill (dis, dis + getPoint (n, k) + 1, 1e9);
	dis[getPoint (1, 0)] = 0;
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.emplace(0, getPoint (1, 0));

	while (!pq.empty()) {
		auto [_, u] = pq.top();
		pq.pop();
		if (flag[u]) {
			continue;
		}
		flag[u] = true;

		for (auto[v, c] : graph[u]) {
			if (dis[v] > dis[u] + c) {
				dis[v] = dis[u] + c; 
				pq.emplace(dis[v], v);
			}
		}
	}

	if (dis[getPoint (n, 0)] == 1e9) {
		cout << -1 << endl;
		return 0;
	}

	cout << dis[getPoint (n, 0)] << endl;

	return 0;
}