#include<bits/stdc++.h> //#define int long long #define endl "\n" using namespace std; int n,m; int A[150][150]; int B[150][150]; int g[1<<24]; int f[1<<24]; 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 void chkmin(int &x,int y){ x=min(x,y); } inline int gt(int S,int x){ return (S>>2*(x-1))&3; } inline int sh(int a,int x){ return (a<<2*(x-1)); } mt19937 RD(time(0)); signed main(){ //freopen("daredevil.in","r",stdin); //freopen("daredevil.out","w",stdout); cin>>n>>m; 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 M=1<<2*(m+1); const int MASK=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++){ memcpy(g,f,sizeof(g)); memset(f,0x3f,sizeof(f)); for(int S=0;S<M;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); //cout<<i<<" "<<j<<" "<<A[i][j]<<" "; //for(int p=1;p<=m+1;p++) // cout<<gt(S,p); //cout<<" "<<g[S]<<endl; if(A[i][j]&1){ int E=T; if(a!=3) for(int k=j-1;k>=1;k--) if(gt(E,k)==0)break; else if(gt(E,k)==1)E-=sh(1,k); chkmin(f[E+sh(3,j)+sh(3,j+1)],g[S]+1); if(b==3) chkmin(f[T+sh(3,j)+sh(0,j+1)],g[S]); else if(a==0) chkmin(f[T+sh(b==0?1:2,j)+sh(1,j+1)],g[S]); else if(a==3){ chkmin(f[T+sh(b==0?0:2,j)+sh(a,j+1)],g[S]); } else chkmin(f[T+sh(b==0?a:2,j)+sh(a,j+1)],g[S]); } if(A[i][j]&2){ if(b==1||b==2){ ; } else chkmin(f[T+sh(0,j)+sh(0,j+1)],g[S]); } } } memcpy(g,f,sizeof(g)); memset(f,0x3f,sizeof(f)); for(int S=0;S<M;S++){ int T=(S<<2)&MASK; for(int j=1;j<=m;j++) if(gt(T,j+1)==1) T+=sh(1,j+1); // if(S==51)cout<<"!"<<T<<endl; chkmin(f[T],g[S]); } } int res=n*m; for(int S=0;S<M;S++){ bool p=1; for(int i=1;i<=m+1;i++){int w=gt(S,i); p&=w==3||w==0; } if(p)chkmin(res,f[S]); } cout<<res<<endl; cout.flush(); return 0; } /* 21111 22331 12123 11333 21112 12132 */