Earthquake

Time limit1sMemory limit128 MB

Summary

Count the integer points (x,y) with x≥0, y≥0 and Ax+By≤C for given positive A, B, C.

Level: Medium6 of 10
Topics: Math, Number theory, Geometry
Solved: No attempts yet

Problem

Infinity City occupies an infinite quarter-plane: at every point $(x, y)$ with integer coordinates $x \ge 0$ and $y \ge 0$ there stands exactly one skyscraper, so the city contains infinitely many of them.

One day an earthquake tore a long crack along the line $Ax + By = C$ . Every skyscraper standing at a point with $Ax + By > C$ collapsed and vanished, leaving only the skyscrapers with $Ax + By \le C$ . The city has become finite. Count how many skyscrapers remain.

Input

A single line contains three space-separated positive integers $A$ , $B$ , and $C$ , where $1 \le A, B \le 10^9$ and $1 \le C \le \min(A, B) \times 10^9$ .

Output

Print a single integer: the number of skyscrapers that remain in the city.

Examples3

Example 1
Input
```
3 4 13
```
Expected output
```
12
```
Example 2
Input
```
1 1 1
```
Expected output
```
3
```
Example 3
Input
```
2 3 6
```
Expected output
```
7
```