Задача 3E. Погоня ≡

Условие

"Я наконец-то вышел за пределы Убежища №76. Дверь за спиной закрылась с металлическим лязгом. Было слышно, как внизу остановились генераторы. Теперь здесь делать нечего — родное Убежище навсегда закрыто, нужно догонять Смотрительницу и вас, моих друзей...

Рёв слева заставил меня подпрыгнуть и резко повернуться. Волосы на голове зашевелились, рука потянулась к пистолету на ремне и только ноги приняли единственно правильное решение — бежать, бежать прочь от невиданного ранее чудовища! Вот когда пригодились высокие показатели выносливости — моя скорость оказалась выше скорости Смертельного Когтя. Скоро нашлась и стратегия боя — нужно было отбежать подальше, тщательно прицелиться и выстрелить в монстра, опять отбежать, пока он не успел догнать, и снова выстрелить, и так далее...

Через пару часов все было кончено. Огромная туша не подавала признаков жизни, а я, тяжело дыша, пытался понять, куда это меня занесло? и как теперь вернуться назад?"

На самом деле в рассказе Резидента некоторые детали, мягко говоря, приукрашены... По состоянию обоймы было видно, что Смертельному Когтю хватило ровно двух выстрелов (видимо, он был старым и больным), да и сам рассказчик не выглядел особенно уставшим... Помогите слушателям узнать, на какое минимальное расстояние нужно было удалиться от Убежища Резиденту, чтобы справиться с врагом?

Формализуем условие: Резидент находится на числовой оси в точке 0. В точке -1 находится Смертельный Коготь. Персонажи ходят по очереди, первым ходит Резидент. В его распоряжении r очков действий. Он может потратить их на перемещение (1 очко действия на перемещение вправо на 1 позицию по числовой оси), на выстрел (каждый выстрел требует g очков действий) или не тратить (полностью или частично). Сэкономленные очки на следующий ход не переносятся. Вторым ходит монстр. В его распоряжении d очков действий. Он их тратит только на перемещение (1 очко действия на перемещение вправо на 1 позицию по числовой оси), и если в какой-то момент чудовище оказывается в той же точке, что и человек, оно его съедает. Если Резидент успевает сделать второй выстрел до того момента, как его настиг Смертельный Коготь, он выжил. Определите наименьшую координату точки, в которую придется переместиться человеку, чтобы выжить.

Формат входных данных

В единственной строке входного файла содержится три натуральных числа: d — очки действий Смертельного когтя за ход, r — очки действий Резидента за ход и g — очки действий на один выстрел.

Формат выходных данных

В единственной строке выведите неотрицательное целое число — минимальное расстояние, на которое придется удалиться Резиденту от Убежища, чтобы справиться с врагом. Гарантируется, что ответ не превысит 10¹⁸.

Ограничения

1 ≤ d, g < r ≤ 10⁹.

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при 1 ≤ r ≤ 100, получат не менее 40 баллов.

Пояснения к примерам

В первом примере события развиваются так:

Первый раунд: Резидент перемещается в точку 11, Коготь — в точку 6.

Второй раунд: Резидент перемещается в точку 14 и стреляет первый раз. Два очка действия не используются. Коготь идет в точку 13.

Последний раунд: Резидент стреляет второй раз. Погоня окончена в точке 14.

Во втором примере Резидент успевает выстрелить дважды в течении первого раунда.

Примеры тестов

7 11 6

14

1 2 1

0