Do Not Touch Anything

Interview

Time limit1sMemory limit32 MB

Summary

Given an R by C grid and an N by N square, find the fewest squares needed to cover the whole grid, allowing overhang and overlap.

Level: Medium4 of 10
Topics: Math, Greedy
Solved: No attempts yet

Problem

The seats in the contest hall form a rectangle with $R$ rows and $C$ columns. Before the contest starts the participants must not touch anything, so the host keeps warning them.

The host has now lost his voice and cannot shout any more. The organizers decided to install cameras to watch the participants instead. One camera records the seats in a rectangular area of $N$ rows and $N$ columns. A camera must be placed in the same orientation as the seating grid, and its area may stick out past the seats or overlap the area of another camera.

Find the minimum number of cameras needed so that every seat is recorded by at least one of them.

Input

The first line contains the seat grid height $R$ , the width $C$ , and the range $N$ that one camera records, separated by spaces. ( $1 \le R, C, N \le 1\,000\,000$ )

Output

Print the minimum number of cameras needed to record every seat, on one line.

Examples5

Example 1
Input
```
7 9 3
```
Expected output
```
9
```
Example 2
Input
```
1 1 1
```
Expected output
```
1
```
Example 3
Input
```
1 1 1000000
```
Expected output
```
1
```
Example 4
Input
```
10 10 3
```
Expected output
```
16
```
Example 5
Input
```
5 1 2
```
Expected output
```
3
```