피자 (Large)

< 그림: Designed by Kstudio / Freepik >

갑은 학과 개강총회를 준비하면서 피자를 $N$ 판 시켰다. 식탁 위에는 피자 $N$ 판이 탑 하나로 쌓여 있고, 갑은 이 높이 $N$짜리 피자탑을 높이가 1인 피자탑 $N$ 개로 모두 분리해야 한다. 지루한 일이라 갑은 혼자 놀기를 하며 해치우기로 했다.

놀이 규칙은 이렇다. 갑은 식탁 위의 피자탑 중 하나를 고른 다음, 그 탑을 두 개의 피자탑으로 분리한다. 고른 피자탑의 높이가 $A$이고 이를 높이 $B$인 탑과 높이 $C$인 탑으로 나눴다면, 갑은 이때 $B \times C$ 만큼 즐거움을 느낀다. $B$와 $C$는 모두 1 이상이다. 높이가 1인 피자탑은 더 분리하지 않는다. 식탁 위에 분리할 수 있는 피자탑이 하나도 남지 않으면 놀이가 끝난다.

피자판의 수 $N$이 주어질 때, 갑이 얻을 수 있는 즐거움 총합의 최댓값을 구하여라.

< 높이가 8인 피자탑을 높이가 4인 피자탑 둘로 분리하는 과정 >

첫째 줄에 피자판의 개수를 뜻하는 양의 정수 $N$이 주어진다. ($1 \le N \le 10^9$)

갑이 얻을 수 있는 즐거움 총합의 최댓값을 한 줄에 출력한다.

$N$이 1이면 처음부터 분리할 수 있는 피자탑이 없으므로 즐거움은 0이다.

$N$이 3인 경우를 보자. 괄호 하나가 피자탑 하나를 뜻하고, 괄호 안의 수는 그 탑의 높이다. 처음에 식탁 위에는 (3) 하나가 있다. 갑이 (3)을 (1)과 (2)로 나누면 $1 \times 2 = 2$ 만큼 즐거워한다. 이어서 (2)를 (1)과 (1)로 나누면 $1 \times 1 = 1$ 만큼 즐거워한다. 이제 남은 탑은 모두 높이가 1이라 놀이가 끝나고, 갑이 얻은 즐거움은 $2 + 1 = 3$이다.

$N$이 $10^9$까지 커질 수 있으므로 답은 32비트 정수 범위를 넘는다.