50 - ZOJ Monthly, February 2006 - 1005
A boy named Clever likes a popular single-player math game very much.The game's rule is very simple:
Given a matrix P with m rows and n columns,all of the m*n elements are integers.
The original matrix is:
3 7 -6 1 -2 -6 8 -4After changing the signs of all the elements of the second row, the matrix is:
3 7 -6 1 2 6 -8 4After changing the signs of all the elements of the third column the result is:
3 7 6 1 2 6 8 4Since all the numbers in the matix are nonnegative now,you win the game and you have done 2 changes to win the game.
Clever finds that sometimes to win the game is impossible.Even if the game can be won he wants to know how many changes should he should do at least. So he asks his friend,you,who is an ace programmer to solve the difficult problem.Can you help him?
The input consists of several test cases.The first line of each test case contains two positive integers m,n,(m<=100,n<=100) representing the number of row and col of the matrix.Next m lines each contain n integers representing the oringal matrix.The input is terminal by EOF.
For each test case there is only one integer to output.If it is possible to win the game output the minimal number of the changes he must do.Otherwise output -1 to indicate it is impossible to win.Sample Input:
2 4 3 7 -6 1 -2 -6 8 -4 2 2 1 -1 1 1 1 1 0Sample Output:
2 -1 0
Author: CAO Peng
Tester: DENG Wenliang