#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
using namespace std;
const int maxn = 1e6+10,maxg = 1e3+10;
int gn,gm,n,m,u,v,res = maxn;
char g[maxg][maxg];
struct Edge{ int u,v,x,y; }edge[maxn],sx[maxn],sy[maxn];
inline bool cmpx(const Edge& u,const Edge& v) { return u.x < v.x; }
inline bool cmpy(const Edge& u,const Edge& v) { return u.y < v.y; }
int fa[maxn],rk[maxn],vtp=0;
pii ver[maxn];
int getfa(int x) {
	while(fa[x] != x) x = fa[x];
	return x;
}
void merge(int u,int v) {
	int uf = getfa(u),vf = getfa(v);
	if(uf == vf) return;
	if(rk[uf] < rk[vf]) swap(uf,vf);
	ver[++vtp] = {uf,vf};
	fa[vf] = uf, rk[uf] += rk[vf];
}
void rever() { tie(u,v) = ver[vtp--],fa[v] = v, rk[u] -= rk[v]; }
int ans[maxn];
void solve(int ql,int qr,int vl,int vr) { //geted [0,ql-1]&[0,vl-1]
	if(ql > qr) return;
	int mid = ql + qr >> 1,ltp,rtp,p,opt;
	for(ltp = vtp, p = lower_bound(sy+1,sy+m+1,Edge{0,0,0,ql},cmpy) - sy;
		p <= m && sy[p].y <= mid;++p)
			if(sy[p].x < vl) merge(sy[p].u,sy[p].v);
	for(rtp = vtp, p = lower_bound(sx+1,sx+m+1,Edge{0,0,vl,0},cmpx) - sx;
		p <= m && vtp != m;++p)
			if(sx[p].y <= mid) merge(sx[p].u,sx[p].v);
	if(vtp != m) {
		while(rtp != vtp) rever();
		return solve(mid+1,qr,vl,vr);
	}
	ans[mid] = opt = sx[--p].x;
	while(rtp != vtp) rever();
	solve(mid+1,qr,vl,opt);
	while(ltp != vtp) rever();
	for(int i = lower_bound(sx+1,sx+m+1,Edge{0,0,vl,0},cmpx) - sx;
		sx[i].x < opt;++i)
			if(sx[i].y < ql) merge(sx[i].u,sx[i].v);
	solve(ql,mid-1,opt,vr);
}
int upl[maxg][maxg], dol[maxg][maxg], lk[maxg][maxg];
signed main() {
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>gn>>gm; n = gn * gm;
	for(int i = 1;i<=gn;++i) cin>>g[i]+1;
	for(int i = 1;i<=gn;++i) {
		for(int j = 1;j<=gm;++j) {
			if(g[i][j] == '1') upl[i][j] = i;
			else upl[i][j] = upl[i-1][j];
		}
	}
	for(int i = gn;i;--i) {
		for(int j = 1;j<=gm;++j) {
			if(g[i][j] == '1') dol[i][j] = i;
			else dol[i][j] = dol[i+1][j];
		}
	}
	for(int i = 1;i<=gn;++i) {
		for(int j = gm;j;--j) {
			if(dol[i][j+1]) lk[i][j] = j + 1;
			else lk[i][j] = lk[i][j+1];
		}
	}
	for(int i = 1;i<=gn;++i) {
		for(int j = 1;j<=gm;++j) {
			if(g[i][j] != '1') continue;
			const int dos = dol[i][lk[i][j]],
					  dl = (i-1) * gm;
			if(dos - i >= 0) edge[++m] = {
			.u = dl + j, .v = (dos-1) * gm + lk[i][j],
			.x = lk[i][j] - j - 1, .y = max(dos - i - 1,0ll)};
			int tmp = dol[i+1][j];
			if(tmp) {
				edge[++m] = {
					.u = dl + j, .v = (tmp-1) * gm + j,
					.x = 0, .y = tmp - i - 1
				};
			}
		}
	}
	for(int i = 1;i<=n;++i) fa[i] = i, rk[i] = 1;
	memcpy(sx+1,edge+1,sizeof(sx[0]) * m), sort(sx+1,sx+m+1,cmpx),
	memcpy(sy+1,edge+1,sizeof(sy[0]) * m), sort(sy+1,sy+m+1,cmpy);
	memset(ans,0x3f,(sy[m].y + 1) * sizeof ans[0]);
	solve(0,sy[m].y,0,sx[m].x);
	for(int i = sy[m].y;~i;--i)
		res = min(res,i + ans[i]);
	if(res == maxn) cout<<"-1";
	else cout<<res;
}

WA