#include<bits/stdc++.h>
#define Yzl unsigned long long
#define pi pair<int,int>
#define mp make_pair
#define fi first
#define se second
typedef long long LL;

using namespace std;

const Yzl Lty=20120712;

const int MAXN=1e6+10;
const int inf=1e9;
int n,m;
char ch[MAXN];
vector<int> a[MAXN],l[MAXN],r[MAXN],up[MAXN];
map<pi,int> t[2];
int cl(int x,int y) {
	if(!x) return 0;
	return (x-1)/y+1;
}
int zx(int x,int y) {
	int r1=0;
	while(y<x) {
		++r1;
		y<<=1;
	}
	return r1;
}
int calc(int x,int y,int n,int op) {
	if(x==1&&y==n) return 0;
	if(t[op][mp(x,y)]) return t[op][mp(x,y)];
	int r1=inf;
	int len=y-x+1;
	bool sf=0;
	if(x!=1) {
		r1=min(r1,calc(max(1,x-len),y,n,op)+1);
		if(len>=x-1) sf=1;
	}
	if(y!=n&&!sf) r1=min(r1,calc(x,min(n,y+len),n,op)+1);
//	cout<<x<<' '<<y<<endl;
	return t[op][mp(x,y)]=r1;
}
signed main () {
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) {
		scanf("%s",ch+1);
		a[i].resize(m+3);
		l[i].resize(m+3);
		r[i].resize(m+3);
		up[i].resize(m+3);
		for(int j=1;j<=m;++j) {
			if(ch[j]=='0') a[i][j]=0;
			else {
				a[i][j]=1;
				l[i][j]=r[i][j]=j;
			}
		}
	}
//	if(!a[1][1]&&a[1][7]&&a[1][9]) {
//		for(int i=30;i<=30;++i) {
//			for(int j=1;j<=m;++j) {
//				cout<<a[i][j];
//			} puts("");
//		}
//		return 0;
//	}
	int ans=inf;
//	cout<<calc(13,14,31,1)<<endl;
	for(int i=1;i<=n;++i) {
		for(int j=2;j<=m;++j) {
			if(a[i][j-1]&&a[i][j]) l[i][j]=l[i][j-1];
		}
		for(int j=m-1;j>=1;--j) {
			if(a[i][j+1]&&a[i][j]) r[i][j]=r[i][j+1];
		}
		if(i!=1)
		for(int j=1;j<=m;++j) {
			if(a[i][j]&&a[i-1][j]) {
				up[i][j]=up[i-1][j]+1;
				l[i][j]=max(l[i][j],l[i-1][j]);
				r[i][j]=min(r[i][j],r[i-1][j]);
			}
		}
		for(int j=1;j<=m;++j) {
			if(!a[i][j]) continue;
			int x=i-up[i][j],y=i,X=l[i][j],Y=r[i][j];
			int r1=calc(x,y,n,0),r2=calc(X,Y,m,1);
			int ls=r1+r2;
			if(ls<ans) {
				ans=ls;
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}