题目背景

翻译自 ROIR 2025 D1T1。

题目描述

在一个大小为 $n \times m$ 的矩形网格的左下角位置有一只蚱蜢。每次蚱蜢可以向右、向上或者向右上方对角线方向跳跃，且每次跳跃的距离最多为 $k$ 个格子。

对于 $k = 3$ 的情况，蚱蜢的可移动方向如下所示：

问：最少需要多少次跳跃，才能使蚱蜢从左下角的格子 $(1, 1)$ 移动到右上角的格子 $(n, m)$？

输入格式

第一行包含三个整数 $n$, $m$, 和 $k$，分别表示网格的行数、列数和蚱蜢每次最多能跳跃的格子数（$1 \leq n, m, k \leq 10^9$）。

输出格式

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

9 8 5

3

2 2 1

1

提示

本题使用 Subtask 捆绑测试。数据中 Subtask 0 是样例。