B1. Прямоугольная игра
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

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