#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <tuple>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;
class PalindromeMatrix { public:
int minChange(vector <string> A, int rowCount, int columnCount)
{
const int H = A.size(), W = A[0].size();
vector<vector<int>> cpp, rpp;
{
vector<int> cp(W-columnCount, 0); cp.resize(W, 1);
do cpp.push_back(cp); while(next_permutation(cp.begin(), cp.end()));
vector<int> rp(H-rowCount, 0); rp.resize(H, 1);
do rpp.push_back(rp); while(next_permutation(rp.begin(), rp.end()));
}
int best = 99999999;
for(auto& cp: cpp)
{
int c_score = 0;
for(int x=0; x<W; ++x) if(cp[x])
for(int y=0; y<H-1-y; ++y)
c_score += maj(A[y][x], A[H-1-y][x]);
vector<int> r_score_0(H), r_score_3(H), r_score_4(H);
for(int y=0; y<H; ++y)
for(int x=0; x<W-1-x; ++x)
if(!cp[x] && !cp[W-1-x]) {
r_score_0[y] += maj(A[y][x], A[y][W-1-x]);
r_score_3[y] += maj(A[y][x], A[y][W-1-x]);
r_score_4[y] += maj(A[y][x], A[y][W-1-x]);
} else {
if(cp[x] && cp[W-1-x])
r_score_3[y] += maj(A[y][x],A[H-1-y][x],A[y][W-1-x],A[H-1-y][W-1-x])
- maj(A[y][x],A[H-1-y][x]) - maj(A[y][W-1-x],A[H-1-y][W-1-x]);
else if(cp[x])
r_score_3[y] += maj(A[y][x],A[H-1-y][x],A[y][W-1-x]) - maj(A[y][x],A[H-1-y][x]);
else
r_score_3[y] += maj(A[y][x],A[H-1-y][W-1-x],A[y][W-1-x]) - maj(A[y][W-1-x],A[H-1-y][W-1-x]);
r_score_4[y] += maj(A[y][x],A[H-1-y][x],A[y][W-1-x],A[H-1-y][W-1-x])
- (cp[x] ? maj(A[y][x],A[H-1-y][x]) : 0) - (cp[W-1-x] ? maj(A[y][W-1-x],A[H-1-y][W-1-x]) : 0);
}
for(auto& rp: rpp) {
int score = c_score;
for(int y=0; y<H; ++y) if(rp[y]) {
if(!rp[H-1-y]) score += r_score_3[y];
else score += (y<H-1-y ? r_score_4 : r_score_0)[y];
}
best = min(best, score);
}
}
return best;
}
static int maj(char a, char b, char c, char d) {
int cnt = (a=='0')+(b=='0')+(c=='0')+(d=='0');
return cnt<2?cnt:4-cnt;
}
static int maj(char a, char b, char c) {
int cnt = (a=='0')+(b=='0')+(c=='0');
return cnt<2?cnt:3-cnt;
}
static int maj(char a, char b) {
return a!=b;
}
};
// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
{ ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
{ os << "{ ";
for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const int& Expected, const int& Received) {
bool ok = (Expected == Received);
if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END verify_case(_, PalindromeMatrix().minChange(A, rowCount, columnCount));}
int main(){
CASE(0)
string A_[] = {"0000"
,"1000"
,"1100"
,"1110"};
vector <string> A(A_, A_+sizeof(A_)/sizeof(*A_));
int rowCount = 2;
int columnCount = 2;
int _ = 1;
END
CASE(1)
string A_[] = {"0000"
,"1000"
,"1100"
,"1110"};
vector <string> A(A_, A_+sizeof(A_)/sizeof(*A_));
int rowCount = 3;
int columnCount = 2;
int _ = 3;
END
CASE(2)
string A_[] = {"01"
,"10"};
vector <string> A(A_, A_+sizeof(A_)/sizeof(*A_));
int rowCount = 1;
int columnCount = 1;
int _ = 1;
END
CASE(3)
string A_[] = {"1110"
,"0001"};
vector <string> A(A_, A_+sizeof(A_)/sizeof(*A_));
int rowCount = 0;
int columnCount = 0;
int _ = 0;
END
CASE(4)
string A_[] = {"01010101"
,"01010101"
,"01010101"
,"01010101"
,"01010101"
,"01010101"
,"01010101"
,"01010101"};
vector <string> A(A_, A_+sizeof(A_)/sizeof(*A_));
int rowCount = 2;
int columnCount = 3;
int _ = 8;
END
CASE(5)
string A_[] = {"000000000000"
,"011101110111"
,"010001010101"
,"010001010101"
,"011101010101"
,"010101010101"
,"010101010101"
,"011101110111"
,"000000000000"
,"000000000000"};
vector <string> A(A_, A_+sizeof(A_)/sizeof(*A_));
int rowCount = 5;
int columnCount = 9;
int _ = 14;
END
CASE(6)
string A_[] = {"11111101001110"
,"11000111111111"
,"00010101111001"
,"10110000111111"
,"10000011010010"
,"10001101101101"
,"00101010000001"
,"10111010100100"
,"11010011110111"
,"11100010110110"
,"00100101010100"
,"01001011001000"
,"01010001111010"
,"10100000010011"};
vector <string> A(A_, A_+sizeof(A_)/sizeof(*A_));
int rowCount = 6;
int columnCount = 8;
int _ = 31;
END
/*
CASE(7)
string A_[] = ;
vector <string> A(A_, A_+sizeof(A_)/sizeof(*A_));
int rowCount = ;
int columnCount = ;
int _ = ;
END
CASE(8)
string A_[] = ;
vector <string> A(A_, A_+sizeof(A_)/sizeof(*A_));
int rowCount = ;
int columnCount = ;
int _ = ;
END
*/
}
// END CUT HERE