#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;
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 dfs(int x,int y) ;
int calc(int l1,int l2,int x,int y,int n) {
	int r1=inf;
	if(l1<=1||l2<=1) {
		if(l1<=1) {
			r1=min(r1,l1+zx(n,y));
//			cout<<l1<<' '<<zx(n-y,y)<<' ';
		}
		if(l2<=1) {
			r1=min(r1,l2+zx(n,n-x+1));
		}
		return r1;
	}
	return r1=dfs(l1+l2+1,l1+1);
}
int dfs(int x,int y) {
	if(x==1) return 0;
	if(t[mp(x,y)]) return t[mp(x,y)];
	int l=y-1,r=y,res=inf;
	if(y>1) {
		int ll=cl(l-1,2),rr=cl(x-r,2);
		res=min(res,calc(ll,rr,l,r,x));
	}
	l=y,r=y+1;
	if(y<x) {
		int ll=cl(l-1,2),rr=cl(x-r,2);
		res=min(res,calc(ll,rr,l,r,x));
	}
	return t[mp(x,y)]=res+1;
}
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;
			}
		}
	}
	int ans=inf;
//	cout<<calc(1,2,2,2,4)<<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 l1=cl(x-1,y-x+1),l2=cl(n-y,y-x+1);
			int l3=cl(X-1,Y-X+1),l4=cl(m-Y,Y-X+1);
			int r1=calc(l1,l2,x,y,n),r2=calc(l3,l4,X,Y,m);
			int ls=r1+r2;
//			if(i==2&&j==2) {
//				cout<<l1<<" "<<l2<<" "<<x<<' '<<y<<" "<<n<<endl;
//				cout<<l3<<' '<<l4<<' '<<X<<" "<<Y<<" "<<m<<endl;
//			}
			if(ls<ans) {
				ans=ls;
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}