Flipping

Time limit2sMemory limit128 MB

Summary

Given A zeros and B ones, find the minimum number of turns needed to flip exactly K chosen values each turn until all become 1, or -1 if impossible.

Level: Hard8 of 10
Topics: BFS, Math, Greedy, Simulation
Solved: No attempts yet

Problem

Hongjun has A zeroes and B ones. The goal is to make every number equal to 1.

In one turn, he chooses exactly K numbers and flips their values. A 0 becomes 1, and a 1 becomes 0. On every turn, he may choose any K numbers among the A+B numbers, regardless of their current values or whether they were chosen before.

Find the minimum number of turns needed to reach the goal. If it is impossible, output -1.

Input

The first line contains three integers A, B, and K.

Output

Print the minimum number of required turns on the first line. If it is impossible to make every number equal to 1, print -1.

Constraints

0 ≤ A, B ≤ 100,000
1 ≤ K ≤ 100,000

Examples7

Example 1
Input
```
4 0 3
```
Expected output
```
4
```
Example 2
Input
```
3 0 3
```
Expected output
```
1
```
Example 3
Input
```
4 1 3
```
Expected output
```
2
```
Example 4
Input
```
3 2 5
```
Expected output
```
-1
```
Example 5
Input
```
100000 100000 578
```
Expected output
```
174
```
Example 6
Input
```
0 0 1
```
Expected output
```
0
```
Example 7
Input
```
4 44 50
```
Expected output
```
-1
```