Alien Prince's Social Party

Time limit1sMemory limit1024 MB

Summary

Given A bottles of wine, B loaves of bread, and at most K single-unit spells, find the largest number of guests who can each get equal shares with nothing left over.

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

Problem

Space prince VITAS holds a social party to get to know the Earthlings. VITAS has $A$ bottles of wine and $B$ loaves of bread. VITAS can use a magic spell at most $K$ times, either turning one bottle of wine into one loaf of bread or one loaf of bread into one bottle of wine.

VITAS gives every invited Earthling the same number of bottles of wine and the same number of loaves of bread. It is allowed to give none of one kind to anyone. However, no wine or bread may be left over after the distribution.

Find the maximum number of Earthlings VITAS can invite while satisfying the conditions above.

Input

The first line contains integers $A$ , $B$ , and $K$ separated by spaces. $(1 \le A, B, K \le 10^{10})$

Output

Print the maximum number of Earthlings VITAS can invite while satisfying the conditions.

Examples3

Example 1
Input
```
3 9 1
```
Expected output
```
4
```
Example 2
Input
```
5 10 3
```
Expected output
```
5
```
Example 3
Input
```
7 8 7
```
Expected output
```
15
```