Задача: Кузнечик 2D

В левом-нижнем углу квадратной клетчатой доски размером \(n\times m\) стоит \(k\)-кузнечик. За один ход \(k\)-кузнечик перемещается по доске вправо, вверх или вправо-вверх по диагонали не более чем на \(k\) клеток.

Необходимо передвинуть \(k\)-кузнечика в правый верхний угол доски в клетку \((n, m)\). За какое минимальное число ходов можно передвинуть \(k\)-кузнечика из клетки \((1, 1)\) в клетку \((n, m)\)?

Формат входных данных
В первой строке заданы три целых числа \(n\), \(m\) и \(k\) — размеры сторон доски и максимальное число клеток, на которое может ходить \(k\)-кузнечик, соответственно (\(1 \le n, m, k \le 10^9\)).

Формат выходных данных
Выведите одно число — минимальное число ходов, необходимое, чтобы передвинуть \(k\)-кузнечика из клетки \((1, 1)\) в клетку \((n, m)\).

Ваш ответ: