In Cookie Clicker, the player earns cookies by clicking on a large cookie with the mouse. By spending the cookies earned, the player can buy various upgrades (farm, factory, etc.) that also produce additional cookies.
Consider a simplified version of this game. Let the player be able to make one mouse click per second, which earns him one cookie. Also, at any time, the player can spend C cookies to buy a factory (at the same time, the player must have at least C cookies, after buying a factory, the number of his cookies instantly decreases by C ). Each factory bought increases the production of cookies per second by P pieces (i.e. if the player has one factory, then he gets 1 + P cookies per second, two factories — 1 + 2 P cookies, three factories &mdash 1 + 3 P cookies, etc.). The player can purchase an unlimited number of factories worth C cookies each. The factory starts producing additional cookies immediately, for example, if after some second of the game the player has C cookies, then the player can buy a factory and in the next second his production of cookies will increase by P pieces.
The original game never ends, but we will assume that the goal of the game is to collect N cookies. Determine the minimum time in which the goal of the game can be reached.
Input
The program receives as input three positive integers written on separate lines: C (factory cost), P (productivity of one factory) and N (required number of cookies).
Imprint
The program should output a single integer — the minimum time in seconds for which the player can get at least N cookies.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
50
3
100
| 75 |
50 seconds into the game, the player will have 50 cookies and be able to buy a factory. After that, he will receive 4 cookies per second, and it will take another 25 seconds to produce 100 cookies. |
| 2 |
99
10
100
| 100 |
The player will be able to collect 100 cookies in 100 seconds, while there is no point in buying a factory. |