Accurate Movement

Interview

Time limit2sMemory limit512 MB

Summary

Two bars of lengths a and b sit on parallel rails in a 2 by n box; move one bar at a time keeping the short bar between the long bar's stoppers, and find the fewest moves to shift both from one side to the other.

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

Problem

Amelia is studying modeling. She is interested in models with moving parts.

As her first task, she made a rectangular box of size 2 × n, which contains two parallel rails and a rectangular bar on each of them. The short bar has size 1 × a, and the long one has size 1 × b. The long bar has a stopper at each end, and the short one is always between these two stoppers.

The bars can be moved along the rails, one bar at a time, as long as the short bar is between the stoppers. So, on each move Amelia selects one of the bars and moves it, while the other one stays in place.

Initially, both bars are aligned to one side of the box, and Amelia wants them to be aligned to the other side in as few moves as possible. What is the minimal number of moves she should do to achieve her goal?

Input

The only input line contains three integers a, b, and n (1 ≤ a < b ≤ n ≤ 107).

Output

The only output line should contain a single integer, the minimal number of moves Amelia needs to do.

Hint

A possible solution for the first example is shown below.

Examples2

Example 1
Input
```
1 3 6
```
Expected output
```
5
```
Example 2
Input
```
2 4 9
```
Expected output
```
7
```