게임판

$N$행 $M$열 크기의 격자판이 있다. 격자판의 각 칸은 비어 있거나 1번 말 혹은 2번 말이 놓여 있다. 편의상 $X$행 $Y$열($1 \leq X \leq N, 1 \leq Y \leq M$)의 칸을 ($X$, $Y$)로 표시한다. 가장 왼쪽 위 칸은 $(1, 1)$이고, 가장 오른쪽 아래 칸은 $(N, M)$이다.

주원이와 준원이는 이 격자판에서 게임을 하려고 한다. 주원이는 1번 말을, 준원이는 2번 말을 선택했다. 게임을 진행하려면 한 변의 길이가 홀수 $K$인 정사각형 격자판이 필요하므로, 격자판의 일부를 골라 그 안에서만 게임을 진행하려고 한다.

게임을 공정하게 진행하기 위해 주원과 준원은 선택할 수 있는 $K$행 $K$열 격자판 중에서 유리도 차이가 가장 작은 격자판을 고르려고 한다. 한 사람의 유리도는 선택한 격자판 안에 있는 자기 말들과 격자판 중앙 사이 거리의 합으로 계산한다. 선택한 격자판의 가장 왼쪽 위 칸이 $(X, Y)$일 때 격자판 중앙의 위치는 $(X+\frac{K-1}{2}, Y+\frac{K-1}{2})$이며, 두 칸 $(X_1, Y_1)$와 $(X_2, Y_2)$ 사이의 거리는 $|X_1 - X_2| + |Y_1 - Y_2|$로 정의한다. 예를 들어, $(1, 3)$과 $(5, 1)$ 사이의 거리는 $(5-1) + (3-1)$인 $6$이다.

아래 그림과 같은 상태의 $4$행 $5$열 격자판이 주어졌고, 이 안에서 게임을 위한 $3$행 $3$열 격자판을 고르려고 한다.

가장 왼쪽 위 칸과 오른쪽 아래 칸을 각각 $(1, 1)$과 $(3, 3)$으로 하면, 중앙인 $(2, 2)$에서 1번 말들까지 거리의 합은 $6$이고 2번 말들까지 거리의 합은 $0$이므로 유리도 차이는 $6$이다.

가장 왼쪽 위 칸과 오른쪽 아래 칸이 각각 $(2, 1)$과 $(4, 3)$인 격자판을 고르면, 1번 말과 중앙 사이 거리의 합은 $0+1=1$이고 2번 말 거리의 합은 $1+1 = 2$여서 유리도 차이는 $1$이 된다. 이 $N$행 $M$열 격자판에서 선택 가능한 모든 격자판을 살펴봐도 유리도 차이가 $1$보다 작은 경우는 없으므로 문제의 정답은 $1$이다.

주원과 준원이 선택할 수 있는 격자판 중 유리도 차이가 가장 작을 때의 차이를 구하라.

첫 번째 줄에 $N$, $M$, $K$가 공백을 사이에 두고 주어진다.

다음 $N$개의 줄에는 격자판의 상태를 나타내는 길이 $M$의 문자열이 주어진다. 문자열은 ., 1, 2로 이루어져 있으며, 의미는 다음과 같다.

• . : 빈 칸
• 1 : 1번 말이 놓여 있는 칸
• 2 : 2번 말이 놓여 있는 칸

첫 번째 줄에 가능한 유리도 차이 중 최솟값을 출력한다.

• 주어지는 모든 수는 정수이다.
• $1 \leq N, M \leq 500$
• $1 \leq K \leq \min(N, M)$
• $K$는 홀수이다.
• 주어지는 격자판의 상태는 ., 1, 2로 이루어져 있다.