#include<bits/stdc++.h> //#define int long long //#define endl "\n" using namespace std; int n,m; int A[200][200]; int B[200][200]; int g[5000300]; int f[5000300]; int pw[20]; inline void rot(){ for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) B[j][i]=A[i][j]; memcpy(A,B,sizeof(A)); swap(n,m); } inline int gt(int S,int x){ return (S/pw[x-1])%3; } inline int sh(int a,int x){ return a*pw[x-1]; } mt19937 RD(time(0)); inline void init(){ memcpy(g,f,sizeof(g)); memset(f,0x3f,sizeof(f)); } inline void chkmin(int &x,int y){ x=min(x,y); } signed main(){ //freopen("daredevil.in","r",stdin); //freopen("daredevil.out","w",stdout); cin>>n>>m; pw[0]=1; for(int i=1;i<=15;i++) pw[i]=pw[i-1]*3; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ char x=RD()%3+'0'; cin>>x; A[i][j]=x-'0'; A[i][j]++; } if(n==1&&m==1){ if(A[1][1]==1)cout<<1<<endl; else cout<<0<<endl; cout.flush(); return 0; } if(m>n)rot(); const int LIM=pw[m+1]; memset(f,0x3f,sizeof(f)); f[0]=0; // for(int i=1;i<=n;i++,cout<<endl) // for(int j=1;j<=m;j++) // cout<<A[i][j]<<" "; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ init(); for(int S=0;S<LIM;S++) if(g[S]<=n*m){ int a=gt(S,j),b=gt(S,j+1); int T=S-sh(a,j)-sh(b,j+1); if(A[i][j]&1){ chkmin(f[T+sh(2,j)+sh(2,j+1)],g[S]+1); // cout<<i<<" "<<j<<" "<<T+sh(2,j)+sh(2,j+1)<<" "<<f[T+sh(2,j)+sh(2,j+1)]<<endl; for(int p=(b==2?2:b);p<=(b==2?2:1);p++) for(int q=(a==2?2:a);q<=(a==2?2:1);q++) if(p+q){chkmin(f[T+sh(p,j)+sh(q,j+1)],g[S]);} } if(A[i][j]&2){ if(a==1||b==1)continue; chkmin(f[T],g[S]); } } } init(); for(int S=0;S<LIM;S++) if(g[S]<=n*m&&gt(S,m+1)!=1) chkmin(f[S*3%LIM],g[S]); // for(int S=0;S<LIM;S++)if(f[S]<=n*m){ // for(int i=1;i<=m;i++) // cout<<gt(S,i+1); // cout<<" "<<f[S]<<endl; // } // cout<<endl; } int res=n*m; for(int S=0;S<LIM;S++){ bool p=1; for(int i=1;i<=m;i++) p&=gt(S,i+1)!=1; if(p)chkmin(res,f[S]); } cout<<res<<endl; cout.flush(); return 0; } /* 3 7 0001101 0201020 0001101 */