32821번 - Diagonal Flipping 다국어

문제

We are given an $m \times n$ grid that consists of 0ドル$s and 1ドル$s. We have two types of diagonal operations like the following two figures. The type $A$ diagonal flipping operation to a grid position $(i,j)$ is to flip all the elements in the positions $(i + k,j - k)$ of the grid for any integer $k$. If we flip the element 0ドル,ドル then it becomes 1ドル$. If we flip the element 1ドル,ドル then it becomes 0ドル$. The type $B$ diagonal flipping operation to a grid position $(i,j)$ is to flip all the elements in the positions $(i + k,j + k)$ of the grid for any integer $k$. Note that a grid position $(p, q)$ is valid only when 0ドル ≤ p ≤ m - 1,ドル 0ドル ≤ q ≤ n - 1$.

Fig 1. Type $A$ diagonal operation to the grid position $(2, 0)$

Fig 2. Type $B$ diagonal operation to the grid position $(2, 1)$

Fig 1 shows the type $A$ diagonal flipping operation to the grid position $(2, 0)$. Note that the type $A$ diagonal flipping operations to the grid positions $(1, 1)$ or $(0, 2)$ have the same effect. Fig 2 shows the type $B$ diagonal flipping operation to the grid position $(2, 1)$. The type $B$ diagonal flipping operations to the grid positions $(1, 0)$ or $(3, 2)$ have the same effect.

Given an information of an $m \times n$ grid, write a program to output the minimum number of the diagonal operations to make all the elements in the grid to zeros.

입력

Your program is to read from standard input. The first line of input contains two positive integers $m$ (1ドル ≤ m≤1,000円$) and $n$ (1ドル ≤ n ≤ 1,000円$) where $m$ and $n$ indicate the number of rows and columns of the grid, respectively. The rows of the grid are numbered from 0ドル$ to $m - 1$ and the columns are numbered from 0ドル$ to $n - 1$. In the following $m$ lines, the $i$-th line contains $n$ numbers, separated by spaces, which are zero or one that correspond to the row $i - 1$ of the grid.

출력

Your program is to write to standard output. Print exactly one line. The line should contain the minimum number of the diagonal operations to make all the elements of the grid to zeros. If it is not possible to make all the elements of the grid zeros, the program should print the number -1.

제한

힌트