#include <fstream>
#include <vector>
using std::vector; using std::ifstream;
using std::ofstream;
//avem o matrice de cel mult 16x16
//putem inversa fie linii fie coloane
//vom avea 32 tipuri de operatii:
//l1,l2,...,l16
//c1,c2,...,c16
//unde: lX -> inverseaza linia X; cX -> inverseaza coloana X
//la inceput, fiecare operatie are un avantaj/dezavantaj
//executarea operatiilor: l2,c3 schimba avantajul operatiei c3
//executarea operatiilor: c2,c3 NU schimba avantajul operatiei c3
//executarea operatiilor c2,c3 este acelasi lucru cu executarea operatiilor c3,c2
//formam toate posibilitatile de a inversa coloanele:
//De cate o op: {c1} {c2} ... {c16} (16 posibilitati)
//De cate 2 op: {c1,c2} {c2,c3} ... {c15,c16} (15 posibilitati)
//De cate 3 op: {c1,c2,c3} {c2,c3,c4} {c3,c4,c5} {c4,c5,c6} {c5,c6,c7}
// {c6,c7,c8} {c7,c8,c9} {c8,c9,c10} {c9,c10,c11} {c10,c11,c12}
// {c11,c12,c13} {c12,c13,c14} {c13,c14,c15} {c14,c15,c16} (14 posibilitati)
//...
//Deci avem: 16+15+14+13+...+1 posibilitati, adica 16*17/2 = 136 posibilitati
//Procedam apoi la fel si pentru linii, si o sa obtinem 136*136 posib. le incercam pe fiecare.
//putem nota o operatie numeric
//astfel, c(1..16) vor avea valorile 1..16 si l(1..16) vor avea valorile 17..33
const unsigned int MAX_OP = 32;
const unsigned int MAX_MAT_SIZE = 16;
struct Mat {
long mat[MAX_MAT_SIZE][MAX_MAT_SIZE];
unsigned int nr_l,nr_c;
};
/*
inline char c(unsigned int i){return char(i%MAX_MAT_SIZE);}
inline char l(unsigned int i){return char(i%MAX_MAT_SIZE+MAX_MAT_SIZE);}
*/
//inverseaza coloanele [start_col;end_col) din matricea in si obtine noua matrice out
void matinvcols (const Mat &in, unsigned int start_col,
unsigned int end_col, Mat &out)
{
for (unsigned int col=0; col<in.nr_c; col++) {
for (unsigned int line=0; line<in.nr_l; line++) {
if (col>=start_col && col<end_col)
out.mat[line][col] = -in.mat[line][col];
else
out.mat[line][col] = in.mat[line][col];
}
}
out.nr_l = in.nr_l;
out.nr_c = in.nr_c;
}
long sum (const Mat &mat) {
long ret=0;
for (unsigned int i=0; i<mat.nr_l; i++)
for (unsigned int j=0; j<mat.nr_c; j++)
ret += mat.mat[i][j];
return ret;
}
int main (void)
{
Mat mat,mat2;
ifstream f_in("flip.in");
ofstream f_out("flip.out");
f_in>>mat.nr_l>>mat.nr_c;
for (unsigned int i=0; i<mat.nr_l; i++)
for (unsigned int j=0; j<mat.nr_c; j++)
f_in >> mat.mat[i][j];
f_in.close();
/*vector<char> op(MAX_OP), bestop(MAX_OP);*/
long max_sum = sum(mat);
//din cate operatii sa fie formata solutia: [1;16]
for (unsigned int nr_op=1; nr_op<=16; nr_op++) {
//de la a cata operatie sa inceapa: [0;15-nr_op+1]
for (unsigned int offset=0; offset<=16-nr_op; offset++) {
//avem solutia [offset;offset+nr_op)
/*op.erase();
for (unsigned int i=0; i<nr_op; i++)
op.push_back( c(offset+i) );*/
matinvcols(mat, offset, offset+nr_op, mat2);
//cautam toate liniile in dezavantaj, le inversam
for (unsigned int lin=0; lin<mat2.nr_l; lin++) {
long lin_sum=0;
for (unsigned int col=0; col<mat2.nr_c; col++)
lin_sum += mat2.mat[lin][col];
if (lin_sum < 0) {
/*op.push_back( l(lin) );*/
//inversam linia lin, adica executam operatia l(lin)
for (unsigned int col=0; col<mat2.nr_c; col++)
mat2.mat[lin][col] *= -1;
}
}
//calculam suma matricii dupa operatii
long sum_this = sum(mat2);
if (sum_this > max_sum) {
// am obtinut un nou maxim
max_sum = sum_this;
// bestop = op;
}
}
}
f_out << max_sum << '\n';
f_out.close();
return 0;
}