Monocarp decided to set up an office for himself. He has already found and rented a room, and now it is finally time to renovate it.
As in any office, the ceiling will be made as a suspended ceiling of PVC tiles, which can be replaced with square lamps. More precisely, the ceiling is a rectangle consisting of $$$n \times m$$$ tiles.
To light his future office, Monocarp wants to replace some of the tiles with lamps. It is impossible to install more than one lamp on the same tile.
At the moment, Monocarp has brought two independent electrical lines to the ceiling, each with its own switch. Each lamp will be connected either to the first line or to the second one.
Monocarp wants his office to be well lit. Namely, he wants to install the lamps in such a way that turning on even one line would leave no dark places. Monocarp defines dark place as a $$$k \times k$$$ square with no lit lamps.
In other words, Monocarp wants to install the lamps in such a way that no matter which line is turned on, there is at least one lit lamp in every $$$k \times k$$$ square of tiles.
What is the minimum number of lamps Monocarp needs to install?
The first and only line contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$2 \le n, m \le 10^9$$$; $$$2 \le k \le \min(n, m)$$$) — the dimensions of the ceiling and the constant $$$k$$$.
Print one integer — the minimum number of lamps that Monocarp needs to install.
2 4 2
4
5 5 3
3
1000000000 999999999 2
499999999000000000
One possible arrangement of lamps for the first example is shown below:
One possible arrangement of lamps for the second example is shown below: