B. Data Center Lamps
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In a busy data center, lamps are essential for smooth server operations. One day, several lamps go out, making it hard for technicians to work. To fix this, the facility uses a special control panel that can toggle all lamps in a selected row or column — flipping each lamp from on to off or off to on.

Your task is to help restore full lighting using the fewest toggles. If it's impossible to turn all lamps on, output $$$-1$$$.

You're given an $$$n \times m$$$ grid representing lamp states: $$$1$$$ for on, $$$0$$$ for off. With each operation, you can toggle any row or column to flip all its lamp states.

Determine the minimum number of toggles needed to turn every lamp on, or report $$$-1$$$ if it's not possible.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2500$$$) — the number of rows and columns in the grid.

The next $$$n$$$ lines each contain $$$m$$$ integers (either $$$0$$$ or $$$1$$$) describing the grid.

Output

For each test case, print a single integer $$$-$$$ the minimum number of toggles required to make all lamps on, or $$$-1$$$ if it is impossible.

Examples
Input
3 3
0 1 0
1 0 1
0 1 0
Output
3
Input
4 4
0 0 1 1
0 0 1 1
1 1 0 0
1 1 0 0
Output
4
Input
4 4
0 0 0 1
0 0 0 1
0 0 0 0
0 0 0 0
Output
-1
Note

$$$$$$ \begin{matrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{matrix} \xrightarrow{\text{Row 2}} \begin{matrix} 0 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 0 \end{matrix} \xrightarrow{\text{Col 1}} \begin{matrix} 1 & 1 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 0 \end{matrix} \xrightarrow{\text{Col 3}} \begin{matrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{matrix} $$$$$$