Table and Chairs

Time limit1sMemory limit128 MB

Summary

Given a rectangular tabletop A by B and square chairs of side K, find the maximum number of non-overlapping chairs whose backrest lies along a table edge.

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

Problem

Bajtazar is buying furniture online. He has already picked a nice table and a set of chairs, and now he wonders how many chairs he can buy so that all of them fit at the table.

The tabletop is a rectangle measuring $A$ centimeters wide and $B$ centimeters deep. The seat of a chair, seen from above, is a square with side $K$ centimeters. From now on we treat the table as a rectangle and each chair as a square.

One side of the seat (the square) has a backrest attached. Every chair must be placed with its backrest toward the table, that is, the side carrying the backrest must lie exactly along one of the four edges of the table. In addition, the seat must lie entirely underneath the tabletop, and no two seats may overlap. We ignore the table legs (assume they are infinitely thin and located at the four corners of the top). At most how many chairs can be placed at the table?

Input

The only line contains three integers $A$ , $B$ , and $K$ ( $1 \le A, B, K \le 500\,000\,000$ ): the width and depth of the tabletop and the side length of a chair seat, respectively.

Output

Print a single line with the maximum number of chairs that can be placed at the table.

Examples2

Example 1
Input
```
15 18 4
```
Expected output
```
10
```
Example 2
Input
```
12 8 4
```
Expected output
```
6
```