Magic Marbles

Time limit2sMemory limit128 MB

Summary

Find the largest number up to M that evenly divides C(S+F, S) without ever computing the huge binomial coefficient directly, using prime exponent analysis.

Level: Hard8 of 10
Topics: Number theory, Combinatorics, Math, Brute force
Solved: No attempts yet

Problem

A wizard made S real magic marbles and F fake marbles that look identical. When all S real marbles are together, they become a source of enormous power.

Someone wants to discover which marbles are real. They will gather N people and test every way to choose S marbles from the total S+F marbles exactly once.

Each person is assigned the combinations they will test in advance. No combination is tested more than once.

Every person must also test the same number of combinations. Given the maximum number M of people that can be gathered, find the largest number of people not exceeding M such that all combinations can be tested and every person does the same amount of work.

Input

The first line contains S, F, and M.

S and F are integers between 1 and 1,000,000,000, inclusive. M is an integer between 1 and 100,000, inclusive.

Output

Print the largest number of people that satisfies the conditions. If it is impossible, print -1.

Hint

When S=3 and F=1, there are 4 ways to choose 3 marbles from the 4 total marbles. Therefore, 2 people can each test 2 combinations.

Examples4

Example 1
Input
```
3 1 3
```
Expected output
```
2
```
Example 2
Input
```
3 3 50
```
Expected output
```
20
```
Example 3
Input
```
4 3 4
```
Expected output
```
1
```
Example 4
Input
```
15634 456 5000
```
Expected output
```
4990
```