Game Board

$N$ rows and $M$ columns of grid. Each cell is empty or holds piece 1 or piece 2. For convenience, the cell in row $X$ and column $Y$ ($1 \leq X \leq N, 1 \leq Y \leq M$) is written ($X$, $Y$). The top-left cell is $(1, 1)$, and the bottom-right cell is $(N, M)$.

Juwon and Junwon want to play a game on this grid. Juwon takes piece 1, and Junwon takes piece 2. The game needs a square grid with odd side length $K$, so they pick a part of the grid and play only inside it.

To keep the game fair, Juwon and Junwon want to choose, among all $K$ by $K$ subgrids they can choose, the one where the difference in advantage is smallest. A player's advantage is the sum of distances from the center of the chosen subgrid to that player's pieces inside it. If the top-left cell of the chosen subgrid is $(X, Y)$, the center is at $(X+\frac{K-1}{2}, Y+\frac{K-1}{2})$. The distance between cells $(X_1, Y_1)$ and $(X_2, Y_2)$ is $|X_1 - X_2| + |Y_1 - Y_2|$. For example, the distance between $(1, 3)$ and $(5, 1)$ is $(5-1) + (3-1)$, which is $6$.

The figure below shows a $4$ by $5$ grid, and Juwon and Junwon want to pick a $3$ by $3$ subgrid inside it.

When the subgrid has top-left $(1, 1)$ and bottom-right $(3, 3)$, the sum of distances from piece 1 to the center $(2, 2)$ is $6$, and the sum for piece 2 is $0$. The difference in advantage is $6$.

If the subgrid has top-left $(2, 1)$ and bottom-right $(4, 3)$, the sum of distances for piece 1 to the center is $0+1=1$, and the sum for piece 2 is $1+1 = 2$. The difference in advantage is $1$. No subgrid of the $N$ by $M$ grid gives a difference smaller than $1$, so the answer is $1$.

Find the smallest difference in advantage over all subgrids Juwon and Junwon can choose.

The first line contains $N$, $M$, and $K$, separated by spaces.

The next $N$ lines each contain a string of length $M$ that describes the grid. The string consists of ., 1, and 2, with these meanings:

• . : an empty cell
• 1 : a cell with piece 1
• 2 : a cell with piece 2

Print the smallest possible difference in advantage on the first line.

• All given numbers are integers.
• $1 \leq N, M \leq 500$
• $1 \leq K \leq \min(N, M)$
• $K$ is odd.
• The grid consists of ., 1, and 2.