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