#include<bits/stdc++.h>
#ifdef xay5421
#define D(...) fprintf(stderr,__VA_ARGS__)
#define DD(...) D(#__VA_ARGS__ "="),debug_helper::debug(__VA_ARGS__),D("\n")
#include"/home/xay5421/debug.hpp"
#else
#define D(...) ((void)0)
#define DD(...) ((void)0)
#endif
#define pb push_back
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define each(x,v) for(auto&x:v)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
template<class T>void rd(T&x){int f=0,c;while(!isdigit(c=getchar()))f^=!(c^45);x=(c&15);while(isdigit(c=getchar()))x=x*10+(c&15);if(f)x=-x;}
template<class T>void pt(T x,int c=-1){if(x<0)putchar('-'),x=-x;if(x>9)pt(x/10);putchar(x%10+48);if(c!=-1)putchar(c);}
using namespace std;
using LL=long long;
using ULL=unsigned long long;
int n,m;
int main(){
#ifdef xay5421
	freopen("a.in","r",stdin);
#endif
	rd(n),rd(m);
	vector<vector<int> >a(n+2,vector<int>(m+2));
	auto up(a);
	vector<vector<int> >le(n+2,vector<int>(m+2,0));
	vector<vector<int> >ri(n+2,vector<int>(m+2,m+1));
	rep(i,1,n){
		rep(j,1,m){
			int c;
			while(!isdigit(c=getchar()));
			a[i][j]=c-'0';
		}
	}
	auto s(a);
	rep(i,1,n){
		int last=0;
		rep(j,1,m){
			s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
			if(a[i][j]){
				up[i][j]=up[i-1][j]+1;
				le[i][j]=max(last+1,le[i-1][j]);
			}else{
				last=j;
			}
		}
		last=m+1;
		per(j,m,1){
			if(a[i][j]){
				ri[i][j]=min(last-1,ri[i-1][j]);
			}else{
				last=j;
			}
		}
	}
	auto work=[&](int l,int x,int r){
		if(!r)return int(1e9);
		// DD(l,x,r);
		int l0=(l+x-1)/x;
		if(l==0){
			int ans=0;
			while(r>0){
				++ans;
				int t=min(x,r);
				r-=t;
				x+=t;
			}
			return ans;
		}
		int k=__lg(l0);
		rep(i,0,k){
			if(l0>>i&1){
				int t=min(x,l);
				l-=t;
				x+=t;
			}else{
				int t=min(x,r);
				r-=t;
				x+=t;
				if(!r)return int(1e9);
			}
		}
		int ans=k+1;
		assert(l<=0);
		while(r>0){
			++ans;
			int t=min(x,r);
			r-=t;
			x+=t;
		}
		return ans;
	};
	auto solve=[&](int l,int x,int r){
		if(l==0&&r==0)return 0;
		// D("! solve %d %d %d\n",l,x,r);
		int ret=min(work(l,x,r),work(r,x,l));
		// D("solve %d %d %d : %d\n",l,x,r,ret);
		return ret;
	};
	int ans=1e9;
	rep(i,1,n){
		rep(j,1,m)if(a[i][j]){
			// D("i=%d j=%d\n",i,j);
			ans=min(ans,solve(i-up[i][j],up[i][j],n-i)+solve(le[i][j]-1,ri[i][j]-le[i][j]+1,m-ri[i][j]));
		}
	}
	printf("%d\n",ans);
	return 0;
}


/*
Breakpoint 1, main () at c.cpp:104
104				D("i=%d j=%d\n",i,j);
(gdb) p u
No symbol "u" in current context.
(gdb) p up
$1 = std::__debug::vector of length 6, capacity 6 = {
  std::__debug::vector of length 6, capacity 6 = {0, 0, 0, 0, 0, 0}, 
  std::__debug::vector of length 6, capacity 6 = {0, 1, 0, 0, 1, 0}, 
  std::__debug::vector of length 6, capacity 6 = {0, 0, 1, 0, 0, 0}, 
  std::__debug::vector of length 6, capacity 6 = {0, 0, 2, 1, 0, 0}, 
  std::__debug::vector of length 6, capacity 6 = {0, 0, 3, 2, 0, 0}, 
  std::__debug::vector of length 6, capacity 6 = {0, 0, 0, 0, 0, 0}}
(gdb) p le
$2 = std::__debug::vector of length 6, capacity 6 = {
  std::__debug::vector of length 6, capacity 6 = {1, 1, 1, 1, 1, 1}, 
  std::__debug::vector of length 6, capacity 6 = {1, 1, 3, 4, 4, 1}, 
  std::__debug::vector of length 6, capacity 6 = {1, 2, 3, 4, 5, 1}, 
  std::__debug::vector of length 6, capacity 6 = {1, 2, 3, 4, 5, 1}, 
  std::__debug::vector of length 6, capacity 6 = {1, 2, 3, 4, 5, 1}, 
  std::__debug::vector of length 6, capacity 6 = {1, 1, 1, 1, 1, 1}}
(gdb) p le[i][j]
$3 = (__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type &) @0x5555555744c8: 3
(gdb) p ri[i][j]
$4 = (__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type &) @0x5555555746e8: 1
(gdb) p j
$5 = 2
(gdb) p i
$6 = 2
(gdb) p ri
$7 = std::__debug::vector of length 6, capacity 6 = {std::__debug::vector of length 6, capacity 6 = {4, 4, 4, 4, 4, 4}, std::__debug::vector of length 6, capacity 6 = {4, 1, 1, 2, 4, 4}, 
  std::__debug::vector of length 6, capacity 6 = {4, 0, 1, 2, 3, 4}, std::__debug::vector of length 6, capacity 6 = {4, 0, 1, 2, 3, 4}, std::__debug::vector of length 6, capacity 6 = {4, 
    0, 1, 2, 3, 4}, std::__debug::vector of length 6, capacity 6 = {4, 4, 4, 4, 4, 4}}
(gdb) p ri
$8 = std::__debug::vector of length 6, capacity 6 = {
  std::__debug::vector of length 6, capacity 6 = {4, 4, 4, 4, 4, 4}, 
  std::__debug::vector of length 6, capacity 6 = {4, 1, 1, 2, 4, 4}, 
  std::__debug::vector of length 6, capacity 6 = {4, 0, 1, 2, 3, 4}, 
  std::__debug::vector of length 6, capacity 6 = {4, 0, 1, 2, 3, 4}, 
  std::__debug::vector of length 6, capacity 6 = {4, 0, 1, 2, 3, 4}, 
  std::__debug::vector of length 6, capacity 6 = {4, 4, 4, 4, 4, 4}}
(gdb) 

*/