1 #include <iostream>
  2 #include <stdio.h>
  3 #include <string.h>
  4 #include <math.h>
  5 #include <algorithm>
  6 using namespace std;
  7 int a[2][170],n,m,zh,b[100],dp[2][170][170];
  8 bool check(int x,int y)
  9 {
 10     int x1=x<<1,x2=x>>1;
 11     if(y&x1)return 0;
 12     if(y&x2)return 0;
 13     return 1;
 14 }
 15 bool check1(int x,int y)
 16 {
 17     if(x&y)return 0;
 18     return 1;
 19 }
 20 bool check2(int x,int y)
 21 {
 22     int z=x|y;
 23     if(z>y)return 0;
 24     return 1;
 25 }
 26 int fun(int x)
 27 {
 28     int s=0;
 29     while(x)
 30     {
 31         s+=x&1;
 32         x>>=1;
 33     }
 34     return s;
 35 }
 36 void init()
 37 {
 38     zh=0;
 39     for(int i=0; i<(1<<m); i++)
 40     {
 41         if(!(i&(i<<2)))
 42         {
 43             a[0][zh]=i;
 44             a[1][zh++]=fun(i);
 45         }
 46     }
 47 }
 48 int main()
 49 {
 50 
 51     while(~scanf("%d%d",&n,&m))
 52     {
 53         init();
 54         int i,j,x,k,r;
 55         memset(dp,0,sizeof(dp));
 56         x=getchar();
 57         for(i=0; i<n; i++)
 58         {
 59             b[i]=0;
 60             for(j=0; j<m; j++)
 61             {
 62                 x=getchar();
 63                 b[i]=(b[i]<<1)+x-‘0‘;
 64                 x=getchar();
 65             }
 66         }
 67         int ix,iy;
 68         for(i=0; i<n; i++)
 69         {
 70             ix=i&1,iy=!ix;
 71             for(j=0; j<zh; j++)
 72             {
 73                 if(check2(a[0][j],b[i]))
 74                     if(!i)
 75                     {
 76                         dp[0][0][j]=a[1][j];
 77                     }
 78                     else if(i==1)
 79                     {
 80                         for(k=0; k<zh; k++)
 81                         {
 82                             if(check(a[0][k],a[0][j]))
 83                                 dp[1][k][j]=dp[0][0][k]+a[1][j];
 84                         }
 85                     }
 86                     else
 87                     {
 88                         for(k=0; k<zh; k++)
 89                         {
 90                             if(check(a[0][k],a[0][j]))
 91                             {
 92                                 for(r=0; r<zh; r++)
 93                                 {
 94                                     if(check1(a[0][r],a[0][j]))
 95                                         dp[ix][k][j]=dp[ix][k][j]>dp[iy][r][k]+a[1][j]?dp[ix][k][j]:dp[iy][r][k]+a[1][j];
 96                                 }
 97                             }
 98 
 99                         }
100                     }
101             }
102         }
103         int sum=0;
104         for(i=0; i<zh; i++)
105             for(j=0; j<zh; j++)
106                 sum=sum>dp[ix][i][j]?sum:dp[ix][i][j];//,cout<<dp[1][i][j]<<" ";
107         printf("%d\n",sum);
108     }
109 }