Welcome to ZOJ
50 - ZOJ Monthly, February 2006 - 1005
Clever's Problem

Time Limit: 5 Seconds      Memory Limit: 32768 KB

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.
You can change the signs of all the elements in any row or column you want.Change sign of a integer x means to replace x with -x.The aim of the game is that after some changes all the elements in the matrix are nonnegative.

For example:
The original matrix is:
         3  7 -6  1
        -2 -6  8 -4
After changing the signs of all the elements of the second row, the matrix is:
        3  7 -6  1
        2  6 -8  4
After changing the signs of all the elements of the third column the result is:
        3 7 6 1
        2 6 8 4
Since 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
Sample Output:

Author: CAO Peng
Tester: DENG Wenliang
Submit    Status