#include <stdio.h>

#define MAX 16

int suma_l(int tab[MAX][MAX], int max, int lin) {
	int i, suma = 0;
	for(i=0; i<max; i++) 
		suma += tab[lin][i];
	return suma;
}

int suma_c(int tab[MAX][MAX], int max, int col) {
	int i, suma = 0;
	for(i=0; i<max; i++) 
		suma += tab[i][col];
	return suma;
}

void invert_l(int tab[MAX][MAX], int max, int lin) {
	int i;
	for(i=0; i<max; i++)
		tab[lin][i] = tab[lin][i] * -1;
}

void invert_c(int tab[MAX][MAX], int max, int col) {
	int i;
	for(i=0; i<max; i++)
		tab[i][col] = tab[i][col] * -1;
}

void print_tab(int tab[MAX][MAX], int maxl, int maxc) {
	int i, j;
	for (i=0; i<maxl; i++) {
		for(j=0; j<maxc; j++)
			printf("%3d", tab[i][j]);
		printf("\n");
	}
	printf("\n");
}

void read_Flip(int tab[MAX][MAX], int *N, int *M, char *filename) {
	int i,j;
	FILE *f1 = fopen(filename, "r");

	fscanf(f1, "%d", N);
	fscanf(f1, "%d", M);
	
	printf("N=%d; M=%d\n", *N, *M);
	
	for(i=0; i<*N; i++)
		for(j=0; j<*M; j++)
			fscanf(f1, "%d", &tab[i][j]);
			
	print_tab(tab, *N, *M);

	fclose(f1);	
}

int suma_tot(int tab[MAX][MAX], int n, int m) {
	int i, suma=0;
	for(i=0; i<n; i++)
		suma += suma_l(tab, m, i);
	return suma;
}

void write_suma(int suma, char *filename) {
	FILE *f2 = fopen(filename, "w");
	fprintf(f2, "%d\n", suma);
	fclose(f2);
}

int check_neg_lines(int Flip[MAX][MAX], int N, int M) {
	int change = 0, i,suma;
	for(i=0; i<N; i++) {
		suma = suma_l(Flip, M, i);
		if(suma<0) {
			invert_l(Flip, M, i);
			change++;
		}
	}
	return change;
}

int check_neg_cols(int Flip[MAX][MAX], int N, int M) {
	int change = 0, j, suma;
	for(j=0; j<M; j++) {
		suma = suma_c(Flip, N, j);
		if(suma<0) {
			invert_c(Flip, N, j);
			change++;
		}
	}
	return change;	
}

int count_neg_l(int Flip[MAX][MAX], int M, int lin) {
	int neg = 0;
	int j;
	for(j=0; j<M; j++) 
		if( Flip[lin][j] < 0) neg++;
	return neg;
}

int count_neg_c(int Flip[MAX][MAX], int M, int col) {
	int neg = 0;
	int j;
	for(j=0; j<M; j++) 
		if( Flip[j][col] < 0) neg++;
	return neg;
}

int get_jmax(int Flip[MAX][MAX], int M, int lin) {
	int jmax = 0, j;
	for(j=1; j<M; j++) 
		if(Flip[lin][j] > Flip[lin][jmax]) jmax = j;
	return jmax;
}

int check_min_lines(int Flip[MAX][MAX], int N, int M) {
	int change = 0, i, negs = 0, max = 0, jmax, suma;
	for(i=0; i<N; i++) {
		negs = count_neg_l(Flip, M, i);
		if(negs>=M/2) {
			jmax = get_jmax(Flip, M, i);
			suma = 0;
			suma = suma_l(Flip, M, i) + suma_c(Flip, N, jmax) - 2*Flip[i][jmax];
			if(suma < 0) {
				invert_l(Flip, M, i);
				invert_c(Flip, N, jmax);
				printf("inverted line %d and col %d\n", i, jmax);
				print_tab(Flip, N, M);
				change++;
			}
		}
	}
	return change;
}

int get_imax(int Flip[MAX][MAX], int M, int col) {
	int imax = 0, i;
	for(i=1; i<M; i++) 
		if(Flip[i][col] > Flip[imax][col]) imax = i;
	return imax;
}

int check_min_cols(int Flip[MAX][MAX], int N, int M) {
	int change = 0, i, negs = 0, max = 0, imax, suma;
	for(i=0; i<M; i++) {
		negs = count_neg_c(Flip, N, i);
		if(negs>=N/2) {
			imax = get_imax(Flip, N, i);
			suma = 0;
			suma = suma_l(Flip, M, imax) + suma_c(Flip, N, i) - 2*Flip[imax][i];
			if(suma < 0) {
				invert_l(Flip, M, imax);
				invert_c(Flip, N, i);
				printf("inverted line %d and col %d\n", imax, i);
				print_tab(Flip, N, M);
				change++;
			}
		}
	}
	return change;
}

int main() {

	int N, M, suma, change;
	int Flip[MAX][MAX];
	
	read_Flip(Flip, &N, &M, "flip.in");
	
	
	do {
		change = check_neg_lines(Flip, N, M);
		change += check_neg_cols(Flip, N, M);
		print_tab(Flip, N, M);
		change += check_min_lines(Flip, N, M);
		change += check_min_cols(Flip, N, M);
	} while(change > 0);
	
	
	
	suma = suma_tot(Flip, N, M);

	write_suma(suma, "flip.out");

	return 0;	
}