| ABBYY Cup 2.0 - Easy |
|---|
| Закончено |
Умный Бобер из ABBYY решил устроить себе выходной. Но бездельничать целый день оказалось слишком скучно, и он решил поиграть в игру с камешками. Изначально у Бобра есть n камешков. Он раскладывает их в a одинаковых рядов по b штук в каждом (a > 1). Учтите, что Бобер обязательно использует все камешки, то есть n = a·b.
10 камешков, разложенных в два ряда по 5 штук в каждом После того, как он разложил камешки, Умный Бобер забирает обратно любой из полученных рядов (то есть b камешков) и выбрасывает все остальные камешки. Затем он снова раскладывает все свои камешки (выбирая, возможно, другие a и b) и снова забирает себе один ряд, и так далее. Игра продолжается до тех пор, пока в какой-то момент у Бобра не останется ровно один камешек.
Игровой процесс можно представить себе как конечную последовательность целых чисел c1, ..., ck, где:
- c1 = n
- ci + 1 — количество камешков, которые останутся у Бобра после i-ого хода, то есть количество камешков в ряду некоторого разложения ci камешков (1 ≤ i < k). Заметим, что ci > ci + 1.
- ck = 1
Результатом игры называется сумма чисел ci. Вам дано число n. Найдите максимальный возможный результат игры.
Единственная строка входных данных содержит единственное целое число n — начальное количество камешков у Умного Бобра.
Ограничения на входные данные для получения 30 баллов:
- 2 ≤ n ≤ 50
Ограничения на входные данные для получения 100 баллов:
- 2 ≤ n ≤ 109
Выведите единственное целое число — максимальный возможный результат игры.
10
16
8
15
Рассмотрим первый пример (c1 = 10). Возможные варианты развития игры:
- Можно разложить камешки в 10 рядов по одному в каждом. Тогда c2 = 1, и игра закончится после первого же хода с результатом 11.
- Можно разложить камешки в 5 рядов по два камешка в каждом. Тогда c2 = 2, и игра продолжается. На втором ходе 2 камешка можно разложить единственным способом (помните, что выкладывать все камешки в один ряд нельзя!) — в 2 ряда по одному камешку. c3 = 1, и игра закончится с результатом 13.
- Наконец, можно разложить камешки в 2 ряда по пять камешков. Аналогичными рассуждениями получим c2 = 5, c3 = 1, и игра закончится с результатом 16 — максимальным из возможных.
