# 【題解】Codeforces 1391D. 505

```#include <iostream>
#include <cstring>
using namespace std;

int n, m, g[1000005][3], dp[1000005][8];
string s;

int main() {
cin >> n >> m;
if (n >= 4 && m >= 4){
for (int i = 0; i < n; i++){
cin >> s;
}
cout << -1 << "\n";
return 0;
}
if (n == 1 || m == 1){
cout << 0 << "\n";
return 0;
}
if (n < 4){
for (int i = 0; i < n; i++){
cin >> s;
for (int j = 1; j <= m; j++){
g[j][i] = s[j-1]-'0';
}
}
swap(n, m);
}
else{
for (int i = 1; i <= n; i++){
cin >> s;
for (int j = 0; j < m; j++){
g[i][j] = s[j]-'0';
}
}
}
memset(dp, 0x3F, sizeof(dp));
for (int i = 0; i < (1<<m); i++){
dp[0][i] = 0;
}
for (int i = 1; i <= n; i++){
for (int j = 0; j < (1<<m); j++){
int cost = 0;
for (int k = 0; k < m; k++){
if (((j>>k)&1) != g[i][k]) cost++;
}
for (int k = 0; k < (1<<m); k++){
int tmp = j^k;
if (!((tmp^(tmp>>1))&1)) continue;
else if (m == 3 && !(((tmp>>1)^(tmp>>2))&1)) continue;
dp[i][j] = min(dp[i][j], dp[i-1][k]+cost);
}
//cout << i << " " << j << " " << dp[i][j] << "\n";
}
//cout << "\n";
}
int mn = 10000000;
for (int i = 0; i < (1<<m); i++){
mn = min(mn, dp[n][i]);
}
cout << mn << "\n";
}
```