#include<bits/stdc++.h>
using namespace std;
const int MAXS=1e6+5,MAXN=1005;
int len[MAXN][12],lg[MAXS],st[MAXN][12];
string s[MAXS];
int bit(int x) { return 1<<x; }
int qry(int l,int r) {
	int k=__lg(r-l+1);
	return min(st[l][k],st[r-bit(k)+1][k]);
}
signed main() {
	int n,m;
	ios::sync_with_stdio(false);
	cin>>n>>m;
	if(n<m) {
		swap(n,m);
		for(int i=1;i<=n;++i) s[i].resize(m+1);
		for(int j=1;j<=m;++j) for(int i=1;i<=n;++i) cin>>s[i][j];
	} else {
		for(int i=1;i<=n;++i) s[i].resize(m+1);
		for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) cin>>s[i][j];
	}
	for(int i=1,k=0;i<=n;++i) {
		while((1<<k)<i) ++k;
		lg[i]=k;
	}
	int K=lg[m];
	for(int i=1;i<=m;++i) {
		for(int k=1;k<=K;++k) len[i][k]=i+1;
		for(int j=1;j<=i;++j) {
			int k=lg[(m-i+j-1)/j+(i+j-1)/j];
			len[i][k]=min(len[i][k],j);
		}
	}
	int ans=lg[n]+lg[m];
	for(int t=1;t<=n;++t) {
		for(int i=1;i<=m;++i) st[i][0]=(s[t][i]=='1')?st[i][0]+1:0;
		for(int k=1;k<=K;++k) for(int i=1;i+bit(k)-1<=m;++i) {
			st[i][k]=min(st[i][k-1],st[i+bit(k-1)][k-1]);
		}
		for(int i=1;i<=m;++i) {
			int *v=len[i];
			for(int w=1;w<=K;++w) if(v[w]<=i) {
				int j=qry(i-v[w]+1,i);
				if(j) ans=min(ans,w+lg[(t+j-1)/j+(n-t+j-1)/j]);
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}