Minimum Hops on a Rectangular Grid

Consider an n x m rectangular grid. A grasshopper is initially located at the bottom‐left cell, labeled (1, 1), and it wishes to reach the top‐right cell (n, m). The grasshopper can jump in one of the following three directions:

• Right: from (i, j) to (i, j + p)
• Up: from (i, j) to (i + q, j)
• Diagonal (up-right): from (i, j) to (i + r, j + r)

In every move, the jump distance p, q or r can be any positive integer not exceeding k (i.e. ≤ \(k\)). For instance, when \(k = 3\), a jump can cover 1, 2, or 3 cells in the respective allowed direction.

Your task is to compute the minimum number of jumps needed for the grasshopper to travel from cell \((1, 1)\) to cell \((n, m)\).

inputFormat

The input consists of a single line containing three positive integers n, m, and k separated by spaces, where:

• n is the number of rows in the grid.
• m is the number of columns in the grid.
• k is the maximum number of cells the grasshopper can jump in a single move (in any allowed direction).

outputFormat

Output a single integer representing the minimum number of jumps required for the grasshopper to reach the top-right cell \((n, m)\) starting from \((1, 1)\).

sample

2 3 3

2