거리 두기 게임

준성이와 효석이는 $N \times M$ 크기의 격자판에서 게임을 한다. 규칙은 다음과 같다.

• 준성이와 효석이는 각자 말을 하나씩 가지고 시작한다.
• 효석이는 준성이가 말을 둘 수 없는 격자 칸 $A$개를 정한다.
• 준성이는 말을 둘 수 있는 격자 칸 중 하나에 말을 둔다. 그다음 효석이는 준성이가 말을 둔 칸을 제외한 모든 격자 칸 중 하나에 말을 둔다.
• 두 말 사이의 택시 거리가 $D$보다 작으면 준성이가, 같거나 크면 효석이가 승리한다.

두 사람이 최선을 다해 게임을 진행했을 때, 효석이가 승리할 수 있는 $A$의 최솟값을 구하여라.

효석이가 승리할 수 없는 경우는 입력으로 주어지지 않는다.

첫 번째 줄에 격자판의 세로 길이 $N$과 가로 길이 $M$이 공백으로 구분되어 주어진다. $(3 \leq N, M \leq 400)$

두 번째 줄에 두 말 사이의 택시 거리 $D$가 주어진다. $(2 \leq D \leq 798)$

효석이가 승리할 수 있는 $A$의 최솟값을 출력한다.

격자판 위의 두 칸의 좌표를 각각 $(x_1, y_1)$, $(x_2, y_2)$라고 하면, 두 칸 사이의 택시 거리는 $|x_1 - x_2| + |y_1 - y_2|$이다.