거리 두기 게임

준성이와 효석이는 $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|)$이다.