В левом-нижнем углу квадратной клетчатой доски размером $$$n\times m$$$ стоит $$$k$$$-кузнечик. За один ход $$$k$$$-кузнечик перемещается по доске вправо, вверх или вправо-вверх по диагонали не более чем на $$$k$$$ клеток.
Возможные ходы $$$k$$$-кузнечика для $$$k = 3$$$. Необходимо передвинуть $$$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)$$$.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| |c|c|} Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 15 | $$$n, m \le 10$$$, $$$k = 1$$$ | первая ошибка | |
| 2 | 16 | $$$n, m, k \le 10$$$ | 1 | первая ошибка |
| 3 | 17 | $$$n, m \le 10^9$$$, $$$k = 1$$$ | 1 | первая ошибка |
| 4 | 18 | Гарантируется, что ответ равен 1 или 2 | первая ошибка | |
| 5 | 34 | нет | 1–4 | первая ошибка |
9 8 5
3
2 2 1
1
