Gift

Input

The first line contains two integers $n$ and $m$ (1 \le n, m \le 5000) — the dimensions of matrix $A$. The next $n$ lines contain $m$ numbers a_{i,j} (0 \le a_{i,j} \le 1) — the values of matrix $A$.

Output

Output a single integer — the minimum number of operations.

If there is no solution, output $-1$.

Examples

Note

To the second test:

We can perform the following transformations:

\begin{smallmatrix} 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 \end{smallmatrix} $\to$ \begin{smallmatrix} 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 \end{smallmatrix} by inverting column 2

\begin{smallmatrix} 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 \end{smallmatrix} $\to$ \begin{smallmatrix} 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 \end{smallmatrix} by inverting row 2.

For the matrix \begin{smallmatrix} 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 \end{smallmatrix} , the condition of beauty holds. It can be proven that this is the minimum answer.

Scoring

1. Subtask $1$ ($20$ points): (n, m \le 10)

2. Subtask $2$ ($15$ points): (n = 1)

3. Subtask $3$ ($45$ points): (n, m \le 100)

4. Subtask $4$ ($80$ points): (n, m \le 500)

5. Subtask $5$ ($140$ points): No additional constraints