#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=1,ns; bitset<maxn> qwq;
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;
//    deb(vtp,u,v);
    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 < ns;++p)
            if(sx[p].y <= mid) merge(sx[p].u,sx[p].v);
    if(vtp < ns) {
        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<=gn;++i)
        for(int j = 1;j<=gm;++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 = abs(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<=m;++i)
//    	cerr<<edge[i].u<<' '<<edge[i].v<<' '<<edge[i].x<<' '<<edge[i].y<<'\n',
		qwq.set(edge[i].u), qwq.set(edge[i].v);
    ns = qwq.count();
//    deb(ns);
    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+10,0,sx[m].x+10);
    for(int i = sy[m].y;~i;--i)
        res = min(res,i + ans[i]);
    if(res == maxn) cout<<"-1";
    else cout<<res;
}