기러기 토마토 스위스 인도인 별똥별

기러기 토마토 스위스 인도인 별똥별 우영우...

위의 단어들은 모두 거꾸로 읽어도 똑같은 팰린드롬이다. 승재는 위의 대사를 너무 감명 깊게 들은 나머지, 팰린드롬에 빠져 2차원 팰린드롬을 떠올리고 말았다. 2차원 팰린드롬이란, $N\times M$크기의 행렬이 주어졌을 때, 좌우대칭과 상하대칭을 모두 만족하는 팰린드롬을 의미한다. 우리는 0과 1만으로 이루어진 2차원 비트 행렬이 주어졌을 때, 이 행렬을 일정한 연산을 통해 2차원 비트 팰린드롬으로 만들고자 한다. 이때 필요한 최소 연산 횟수를 구하여라.

연산은 다음 과정을 통해 이루어진다.

1. 배열의 중점을 원점이라 했을 때, 두 개의 사분면을 골라 $K\*K$ 크기의 정사각형을 배치한다. 이때 두 개의 정사각형은 x축 대칭, y축 대칭 또는 원점 대칭을 만족해야 하며, 각 사각형은 하나의 사분면 내부에 완전히 포함되어야 한다.
2. 두 사각형 내부의 모든 비트를 전환한다.

O가 비트를 전환하는 부분이라고 했을 때, 아래는 유효한 연산이다.

$(K=2)$

아래는 유효하지 않은 연산이다.

$(K=1)$

$(K=1)$

입력은 아래와 같이 주어진다.

$N$ $M$ $K$

$A\_{1,1}$ $A\_{1,2}$ ... $A\_{1,M}$

...

$A\_{N,1}$ $A\_{N,2}$ ... $A\_{N,M}$

첫 줄에 2차원 비트 팰린드롬을 만들기 위한 최소 연산 횟수를 출력한다. 만약 2차원 비트 팰린드롬을 만들 수 없는 경우, -1을 출력한다.

• $2 \leq N$, $M \leq 2\\,000$
• $N$, $M$은 짝수
• $1 \leq K \leq min(N/2$, $M/2)$
• $A\_{i,j}$는 0 또는 1이다.