题目描述

来自 ABBYY 的聪明海狸决定休息一天。但整天无所事事实在太无聊了，于是他决定玩一个石子游戏。一开始，海狸有 $n$ 颗石子。他将这些石子分成 $a$ 行，每行有 $b$ 颗石子（$a>1$）。注意，海狸必须用完所有的石子，即 $n=a·b$。

如图，10 颗石子被分成两行，每行 5 颗石子。

当聪明海狸将石子分好后，他会取回其中任意一行（即 $b$ 颗石子），其余石子全部丢弃。然后他用手中的石子再次分行（可以选择不同的 $a$ 和 $b$），再取回一行，如此反复。游戏一直进行，直到某一时刻海狸手中只剩下一颗石子。

游戏过程可以表示为一个有限的整数序列 $c_{1},...,c_{k}$，其中：

• $c_{1}=n$；
• $c_{i+1}$ 表示第 $i$ 次操作后海狸手中剩下的石子数，即某种分法下每行的石子数（$1\leq i<k$）。注意 $c_{i}>c_{i+1}$；
• $c_{k}=1$。

游戏的结果是所有 $c_{i}$ 的和。给定 $n$，请你求出游戏可能得到的最大结果。

输入格式

输入包含一行，一个整数 $n$，表示聪明海狸最初拥有的石子数。

对于获得 30 分，输入限制为：

• $2\leq n\leq 50$

对于获得 100 分，输入限制为：

• $2\leq n\leq 10^{9}$

输出格式

输出一个整数，表示游戏可能得到的最大结果。

说明/提示

以第一个样例（$c_{1}=10$）为例，游戏可能的过程如下：

• 将石子分成 10 行，每行 1 颗石子。此时 $c_{2}=1$，游戏在第一次操作后结束，结果为 11。
• 将石子分成 5 行，每行 2 颗石子。此时 $c_{2}=2$，游戏继续。第二次操作时有 2 颗石子，只能分成 2 行，每行 1 颗石子（注意不能全部放在一行！），$c_{3}=1$，游戏结束，结果为 13。
• 最后，将石子分成 2 行，每行 5 颗石子。类似地，$c_{2}=5,c_{3}=1$，游戏结束，结果为 16——这是可能得到的最大结果。

由 ChatGPT 4.1 翻译

样例

10

16

8

15