当前没有测试数据。

题目描述

有一个超级长的隧道，里面从左到右摆了 $n$ 个宝箱，宝箱里分别有 $1,2,3,...,n$ 颗钻石。同时小瓜手中有 $n$ 枚筹码，筹码上的数字分别为 $1,2,3,...,n$。

小瓜会从第一个宝箱的位置向右走，抵达第 $i$ 个宝箱的位置时，小瓜有两种选择：

• ① 从这个宝箱里拿 $1$ 颗钻石；
• ② 支付数字为 $x$ 的筹码，然后拿走这个宝箱中所有的钻石，其中 $x$ 是 $i$ 的最大真因数（即除自身外最大的因数）。

每个宝箱最多只能拿取一次钻石。

请你帮小瓜做出最合适的选择，使得他拿到的钻石总数最多。

输入格式

一个整数 $n$，表示宝箱的数量。

输出格式

一个整数，表示拿到的钻石总数的最大值。

样例

10

37

20

样例 $1$ 解释

对于 $1 \sim 9$ 号宝箱，策略分别为：

• $1$ 号宝箱：拿走 $1$ 颗钻石；
• $2$ 号宝箱：拿走 $1$ 颗钻石；
• $3$ 号宝箱：拿走 $1$ 颗钻石；
• $4$ 号宝箱：支付 $2$ 号筹码，拿走 $4$ 颗钻石；
• $5$ 号宝箱：拿走 $1$ 颗钻石；
• $6$ 号宝箱：拿走 $1$ 颗钻石；
• $7$ 号宝箱：拿走 $1$ 颗钻石；
• $8$ 号宝箱：支付 $4$ 号筹码，拿走 $8$ 颗钻石；
• $9$ 号宝箱：支付 $3$ 号筹码，拿走 $9$ 颗钻石。
• $10$ 号宝箱：支付 $5$ 号筹码，拿走 $10$ 颗钻石。

此策略能拿走总共 $37$ 颗钻石。

数据规模与约束

对于 $40\%$ 的数据，$1≤n≤100$；

对于 $80\%$ 的数据，$1≤n≤5×10^4$；

对于 $100\%$ 的数据，$1≤n≤10^6$。