대각선 뒤집기

$m \times n$ 크기의 격자가 주어진다. 격자의 원소는 $0$ 또는 $1$이다. 대각선 연산은 두 종류가 있다.

격자의 위치 $(i,j)$에 대한 종류 $A$ 연산은 임의의 정수 $k$에 대해 위치 $(i + k, j - k)$에 있는 원소를 모두 뒤집는다. $0$은 $1$이 되고, $1$은 $0$이 된다.

격자의 위치 $(i,j)$에 대한 종류 $B$ 연산은 임의의 정수 $k$에 대해 위치 $(i + k, j + k)$에 있는 원소를 모두 뒤집는다. 위치 $(p, q)$는 $0 \le p \le m - 1$이고 $0 \le q \le n - 1$일 때만 유효하다.

그림 1. 위치 $(2, 0)$에 대한 종류 $A$ 대각선 연산

그림 2. 위치 $(2, 1)$에 대한 종류 $B$ 대각선 연산

그림 1은 위치 $(2, 0)$에 대한 종류 $A$ 연산을 보여준다. 위치 $(1, 1)$ 또는 $(0, 2)$에 대한 종류 $A$ 연산도 같은 효과를 낸다. 그림 2는 위치 $(2, 1)$에 대한 종류 $B$ 연산을 보여준다. 위치 $(1, 0)$ 또는 $(3, 2)$에 대한 종류 $B$ 연산도 같은 효과를 낸다.

$m \times n$ 격자가 주어졌을 때, 격자의 모든 원소를 $0$으로 만드는 데 필요한 대각선 연산의 최소 횟수를 구하라.

첫 줄에 격자의 행 수 $m$ ($1 \le m \le 1\,000$)과 열 수 $n$ ($1 \le n \le 1\,000$)을 나타내는 양의 정수 두 개가 주어진다. 행은 $0$부터 $m - 1$까지, 열은 $0$부터 $n - 1$까지 번호가 매겨진다.

이어지는 $m$개의 줄에는 각각 공백으로 구분된 $n$개의 수가 주어지며, 수는 $0$ 또는 $1$이다. $i$번째 줄은 격자의 행 $i - 1$에 해당한다.

격자의 모든 원소를 $0$으로 만드는 최소 대각선 연산 횟수를 한 줄에 출력한다. 불가능하면 $-1$을 출력한다.