/*
Things to notice:
1. do not calculate useless values
2. do not use similar names
 
Things to check:
1. submit the correct file
2. time (it is log^2 or log)
3. memory
4. prove your naive thoughts 
5. long long
6. corner case like n=0,1,inf or n=m
7. check if there is a mistake in the ds or other tools you use
8. fileio in some oi-contest

9. module on time 
10. the number of a same divisor in a math problem
11. multi-information and queries for dp and ds problems
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
const int mod=998244353;
const int inf=0x3f3f3f3f;
int calc(int n,int l,int r)
{
	if(l==1&&r==n) return 0;
	int c1=l-1,c2=n-r,c0=r-l+1;
//	int res=0;
//	while(c1||c2)
//	{
//		if(c1<c2) swap(c1,c2);
//		res++;
//		if(c1&&c1<=c0) c0+=c1,c1=0;
//		else if(c2&&c2<=c0) c0+=c2,c2=0;
//		else 
//		{
//			c1-=c0,c0*=2;
//		}
//	}
	int res=inf;
	int n2=n-c1%c0-c2%c0;
	for(int i=0;i<=20;i++)
	{
		int d0=(c0<<i);
		if(d0>n2) break;
		int L=max(0,(1<<i)-1-c2/c0),R=(1<<i)-1,low=inf;
		while(L<=R)
		{
			int mid=(L+R)>>1;
			if(c1-mid*c0<=d0) low=mid,R=mid-1;
			else L=mid+1; 
		}
		if(low==inf) continue;
		int c3=d0-low*c0+c1;
		int nw=i+1;
		while(c3<n) c3*=2,nw++;
		res=min(res,nw);
	}
//	cerr<<n<<" "<<l<<" "<<r<<"... "<<res<<"\n";
	swap(c1,c2);
	for(int i=0;i<=20;i++)
	{
		int d0=(c0<<i);
		if(d0>n2) break;
		int L=max(0,(1<<i)-1-c2/c0),R=(1<<i)-1,low=inf;
		while(L<=R)
		{
			int mid=(L+R)>>1;
			if(c1-mid*c0<=d0) low=mid,R=mid-1;
			else L=mid+1; 
		}
		if(low==inf) continue;
		int c3=d0-low*c0+c1;
		int nw=i+1;
		while(c3<n) c3*=2,nw++;
		res=min(res,nw);
	}
//	cerr<<n<<" "<<l<<" "<<r<<"... "<<res<<"\n";
	return res;
}
int calc2(int n,int l,int r)
{
	if(l==1&&r==n) return 0;
	int res=inf;
	if(r<n) res=min(res,calc2(n,l,min(n,r+r-l+1)));
	if(l>1) res=min(res,calc2(n,max(1,l-(r-l+1)),r));
	return res+1;
}
int n,m;
string g[1000005];
int R[1000005],prv[1000005],nxt[1000005],stk[1000005],top;

void solve()
{
//	for(int i=1;i<=500;i++) for(int j=1;j<=i;j++) for(int k=j;k<=i;k++) assert(calc(i,j,k)==calc2(i,j,k));//cerr<<i<<" "<<j<<" "<<k<<"\n";
//	cerr<<"passed assertions\n";
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>g[i],g[i]='.'+g[i];
	int ans=inf;
	for(int i=m;i>=1;i--)
	{
		for(int j=1;j<=n;j++) 
		{
			if(g[j][i]=='1') R[j]++;
			else R[j]=0; 
		}
		top=0;
		for(int j=1;j<=n;j++)
		{
			while(top&&R[stk[top]]>=R[j]) top--;
			if(!top) prv[j]=0;
			else prv[j]=stk[top];
			stk[++top]=j;
		}
		top=0;
		for(int j=n;j>=1;j--)
		{
			while(top&&R[stk[top]]>=R[j]) top--;
			if(!top) nxt[j]=n+1;
			else nxt[j]=stk[top];
			stk[++top]=j;
		}
		for(int j=1;j<=n;j++) if(R[j])
		{
			int l1=i,r1=i+R[j]-1;
			int l2=prv[j]+1,r2=nxt[j]-1;
//			cerr<<"... "<<l1<<" "<<r1<<" "<<l2<<" "<<r2<<"\n"; 
			ans=min(ans,calc(m,l1,r1)+calc(n,l2,r2));
//			cerr<<"... "<<calc(m,l1,r1)<<" "<<calc(n,l2,r2)<<"\n";
		}
	}
	cout<<ans<<"\n";
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int _=1;
//	cin>>_;
	while(_--) solve();
	return 0;
}