The Smart Beaver from ABBYY decided to have a day off. But doing nothing the whole day turned out to be too boring, and he decided to play a game with pebbles. Initially, the Beaver has n pebbles. He arranges them in a equal rows, each row has b pebbles (a > 1). Note that the Beaver must use all the pebbles he has, i. e. n = a·b.
Once the Smart Beaver has arranged the pebbles, he takes back any of the resulting rows (that is, b pebbles) and discards all other pebbles. Then he arranges all his pebbles again (possibly choosing other values of a and b) and takes back one row, and so on. The game continues until at some point the Beaver ends up with exactly one pebble.
The game process can be represented as a finite sequence of integers c_{1}, ..., c_{k}, where:
The result of the game is the sum of numbers c_{i}. You are given n. Find the maximum possible result of the game.
The single line of the input contains a single integer n — the initial number of pebbles the Smart Beaver has.
The input limitations for getting 30 points are:
The input limitations for getting 100 points are:
Print a single number — the maximum possible result of the game.
10
16
8
15
Consider the first example (c_{1} = 10). The possible options for the game development are:
Name |
---|