#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int n, m, M; int state[177], tot; int cnt[177]; int dp[103][177][177]; bool f1[177][177], f2[177][177]; bool ok1(int a, int b) { if((state[a]<<1)&state[b]) return 0; if((state[a]>>1)&state[b]) return 0; return 1; } bool ok2(int a, int b) { return !(state[a]&state[b]); } void init() { int i, j; tot = 0; int M = (1<<m); for(i = 0; i < M; i++) { if((i>>2)&i) continue; state[tot++] = i; } memset(cnt, 0 ,sizeof(cnt)); for(i = 0; i < tot; i++) { for(j = state[i]; j ; j -= (j&-j)) cnt[i]++; } for(i = 0; i < tot; i++) for(j = 0; j < tot; j++) { f1[i][j] = ok1(i, j); f2[i][j] = ok2(i, j); } //printf("tot = %d\n", tot); } int a[103]; int main() { int i, j, k, x; while( ~scanf("%d%d", &n, &m)) { init(); memset(a, 0, sizeof(a)); for(i = 0; i < n; i++) { for(j = 0; j < m; j++) { scanf("%d", &x); if(!x) a[i] |= (1<<j); } } memset(dp, -1, sizeof(dp)); for(i = 0; i < tot; i++) if(!(a[0]&state[i])) dp[0][0][i] = cnt[i]; for(i = 1; i < n; i++) for(j = 0; j < tot; j++) for(k = 0 ; k < tot; k++) if(f1[j][k] && ~dp[i-1][j][k]) for(x = 0; x < tot; x++) if(f2[j][x] && f1[k][x] && !(a[i]&state[x])) dp[i][k][x] = max(dp[i][k][x], dp[i-1][j][k]+cnt[x]); int ans = 0; for(i = 0; i < tot; i++) for(j = 0; j < tot; j++) //if(f1[i][j]) ans = max(ans, dp[n-1][i][j]); printf("%d\n", ans); } return 0; }