Персонаж известной компьютерной игры Марио постарел и почти перестал прыгать. Но совсем недавно он увидел спуск из $$$N$$$ ступенек, и его накрыло ностальгией. Марио встал на самую верхнюю ступеньку и решил преодолеть этот спуск при помощи прыжков.
Когда-то Марио знал тысячи различных видов прыжков, но теперь он смог вспомнить только два: короткие и длинные. Короткий прыжок позволяет спуститься на произвольное число ступенек, не большее $$$X$$$, а длинный — на произвольное число, не большее $$$Y$$$ ($$$X \lt Y$$$). Но в силу возраста Марио не может делать два длинных прыжка подряд и вынужден между ними совершать хотя бы один короткий. При этом Марио не хочет слишком уж сильно ухудшить свои прошлые результаты и поэтому постарается обойтись как можно меньшим числом прыжков.
Помогите Марио посчитать минимальное количество прыжков, требующееся для преодоления всех $$$N$$$ ступенек.
В первой строке входных данных записано целое число $$$X$$$ — максимальная длина короткого прыжка.
Во второй строке записано целое число $$$Y$$$ ($$$1 \leq X \lt Y \leq 10^{18}$$$) — максимальная длина длинного прыжка.
В третьей строке записано целое число $$$N$$$ ($$$1 \leq N \leq 10^{18}$$$) — количество ступенек в спуске.
В единственной строке выведите целое число — минимальное число прыжков, необходимое Марио для спуска.
Решения, правильно работающие только для случаев, когда $$$X$$$, $$$Y$$$ и $$$N$$$ не превосходят $$$10^5$$$, будут оцениваться в $$$35$$$ баллов.
Решения, правильно работающие только для случаев, когда $$$X$$$, $$$Y$$$ и $$$N$$$ не превосходят $$$10^9$$$, будут оцениваться в $$$50$$$ баллов.
2 3 5
2
1 2 4
3
1 100 1000000000000000000
19801980198019801
На изображениях ниже приведены возможные способы решения первых двух тестов из условия:
Обратите внимание, что входные данные, а также ответ могут быть достаточно большими, поэтому следует использовать 64-битный тип данных, например long long в C/C++, long в Java, int64 в Pascal.
