30052번 - 거리 두기 게임

문제

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