#include <stdio.h>
#include <stdlib.h>
int sum_elements(int** matrix, int n, int m)
{
int i, j;
int sum = 0;
for (i = 0; i < n ;i++)
for (j = 0; j < m ;j++)
sum += matrix[i][j];
return sum;
}
int flip_col(int **matrix, int n, int m, int sum, int c)
{
for (int i = 0 ; i < n ; i ++)
{
sum = sum - 2 * matrix[i][c];
matrix[i][c] = -1 * matrix[i][c];
}
return sum;
}
int flip_row(int **matrix, int n, int m, int sum, int r)
{
for (int i = 0 ; i < m ; i ++)
{
sum = sum - 2 * matrix[r][i];
matrix[r][i] = -1 * matrix[r][i];
}
return sum;
}
int max(int a, int b)
{
if (a >= b)
return a;
return b;
}
int backtrack_cols(int** matrix, int n, int m, int sum, int max_sum,int k)
{
int tmp_sum;
for (int i = k ; i < m ; i ++){
tmp_sum = flip_col(matrix, n, m, sum, i);
max_sum = max(tmp_sum, max_sum);
max_sum = backtrack_cols(matrix, n, m, tmp_sum, max_sum, k + 1);
tmp_sum = flip_col(matrix, n, m, sum, i);
}
return max_sum;
}
int backtrack_rows(int** matrix, int n, int m, int sum, int max_sum, int k)
{
int tmp_sum;
for (int i = k ; i < n ; i ++){
tmp_sum = flip_row(matrix, n, m, sum, i);
max_sum = max(tmp_sum, max_sum);
max_sum = backtrack_cols(matrix, n, m, tmp_sum, max_sum, 0);
max_sum = backtrack_rows(matrix, n, m, tmp_sum, max_sum, k + 1);
tmp_sum = flip_row(matrix, n, m, sum, i);
}
return max_sum;
}
int main(int argc, char** argv)
{
int n, m, i, j, sum;
int **matrix;
FILE *in, *out;
in = fopen("flip.in", "r");
out = fopen("flip.out", "w");
fscanf(in, "%d %d", &n, &m);
// Initialize the matrix
matrix = malloc(n * sizeof(int*));
for (i = 0; i < n; i++)
matrix[i] = malloc(m * sizeof(int));
for (i = 0; i < n; i++)
for (j = 0; j < m; j++)
fscanf(in, "%d", &matrix[i][j]);
// Calculate the initial sum
sum = sum_elements(matrix, n , m);
sum = backtrack_rows(matrix, n, m, sum, sum, 0);
fprintf(out, "%d", sum);
fclose(in);
fclose(out);
}