Доставка в Простоквашино
Ограничение по времени: 1
секунда
Ограничение по памяти: 256
мегабайт
Недавно почтальон Печкин прочитал в газете о новых роботах‑доставщиках и решил использовать одного из них для развоза почты. Он планирует внедрять данную инновацию в деревне Простоквашино, которую можно представить как длинную улицу: в начале —
отделение почты, за ним — жилые дома, расположенные в ряд на равном расстоянии друг от друга.
Чтобы проехать от отделения почты до первого дома или от одного дома до соседнего, роботу Печкина требуется a единиц энергии. Если робот имеет меньше a единиц энергии, он не сможет доехать до следующего дома. При этом предусмотрительный почтальон возле каждого дома разместил зарядную станцию, на которой уровень заряда робота может увеличиться на b единиц.
В качестве «тестового задания» Печкин хочет доставить с помощью робота журнал «Мурзилка» дяде Фёдору, который живёт в k
‑м по счёту от почты доме. Теперь ему предстоит выяснить, на какое минимальное число единиц энергии ему необходимо изначально зарядить робота, чтобы тот мог доехать от почты до дома дяди Фёдора.
Формат входных данных
В первой строке входных данных содержится целое число a
(0⩽a⩽109) — количество энергии, необходимое роботу для того, чтобы проехать расстояние между двумя домами.
Во второй строке содержится целое число b (0⩽b⩽109) — количество энергии, на которое робот может зарядиться у каждого дома.
В третьей строке содержится целое число k (1⩽k⩽109) — номер (по счёту от здания почты) дома дяди Фёдора.
Гарантируется, что a⋅k⩽2⋅109
.
Формат выходных данных
Выведите одно число —
минимальное количество единиц энергии, на которое Печкину необходимо зарядить робота.
Система оценки
Решения, правильно работающие при a
, k⩽100, будут оцениваться в 30 баллов.
Решения, правильно работающие при k⩽5⋅105, будут оцениваться в 75 баллов.
Решения, корректно работающие при a⩽b, будут оцениваться в 35
баллов.
Замечание
В первом примере из условия достаточно зарядить робота на 6
единиц энергии. На дорогу до первого дома он потратит 2 единицы, и у первого дома он зарядится на 1 единицу, у него останется 5 единиц. После зарядки у второго дома останется 4 единицы энергии, у третьего — 3, у четвёртого — 2, и доставщику хватит энергии, чтобы добраться до пятого дома. Можно показать, что меньшего количества энергии роботу не хватит.
