题目描述

你得到了一个大小为 $n\times m$ 的网格，以及一个神奇的正整数 $k$ 。

一个不知名的人想让你用一些颜色给网格着色，着色时要满足以下条件：

• 如果 $(x_1,y_1)$ , $(x_2,y_2)$ 是两个颜色相同的单元格，那么 $\max(|x_1-x_2|,|y_1-y_2|)\ge k$ 。

你不喜欢使用过多的颜色，所以请找出给所有网格都着色所需的最少颜色数。

输入格式

输入只有一行，包含三个正整数 $n$ , $m$ , $k$，代表网格尺寸和魔法常数。

输出格式

输出一个数字，表示涂满网格所需的最少颜色数。

样例 #1

样例输入 #1

3 3 2

样例输出 #1

4

样例输入 #2

5 1 10000

样例输出 #2

5

提示

【样例解释 1】

如图所示，需要 $4$ 种颜色

【样例解释 2】

每个格子都要用不同的颜色，所以要 $5$ 种。

【数据范围】

• 对于 $10\%$ 的测试点，$n = m = k$。
• 对于 $40\%$ 的测试点，$n,m,k \le 10^4$。
• 对于 $100\%$ 的测试点，$n,m,k \le 10^8$。