Умный Бобер из 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. Найдите максимальный возможный результат игры.