题目描述

译自 ROI Regional 2025 Day1 T1. Кузнечик 2D

在一个 $n \times m$ 的方格棋盘的左下角，有一只 $k$-蚱蜢。每次移动，这只 $k$-蚱蜢可以向右、向上或沿右上方向的对角线前进，移动的距离不超过 $k$ 个格子。

当 $k = 3$ 时，$k$-蚱蜢的所有可能走法如上。

现在，需要将这只 $k$-蚱蜢移动到棋盘的右上角，即位置 $(n, m)$。

问：最少需要多少次移动，才能将 $k$-蚱蜢从格子 $(1, 1)$ 移动到格子 $(n, m)$。

输入格式

第一行包含三个整数 $n, m, k$ $(1 \leq n, m, k \leq 10^9)$，分别表示棋盘的尺寸，以及 $k$-蚱蜢每次最多可以移动的格子数。

输出格式

输出一个整数，表示将 $k$-蚱蜢从格子 $(1, 1)$ 移动到格子 $(n, m)$ 所需的最少移动次数。

9 8 5

3

2 2 1

1

数据范围与提示

详细子任务附加限制及分值如下表所示。