← 返回题目列表

Codeforces · 32/C

C. 跳蚤

中文机器翻译题面 查看原题

已知Berland的跳蚤只能垂直和水平跳跃,并且跳跃的长度总是等于s厘米。一只跳蚤发现自己位于 n × m 厘米大小的格子板的某个单元格的中心(每个单元格为 1 × 1 厘米)。她可以随心所欲地跳跃任意次数,甚至可以多次访问一个牢房。唯一的限制是她不能跳出棋盘。

跳蚤可以计算从起始位置 (x, y) 可以到达的细胞数量。我们用 dx, y 表示这个量。您的任务是找到这样的起始位置 (x, y) 的数量,这些起始位置具有最大可能的 dx, y 值。

输入

第一行包含三个整数 n、m、s (1 ≤ n, m, s ≤ 106) — 板的长度、板的宽度和跳蚤跳跃的长度。

输出

输出唯一的整数——跳蚤所需起始位置的数量。

示例

输入 #1

2 3 1000000

输出 #1

6

输入 #2

3 3 2

输出 #2

4