SIOKULE - Kule

no tags 

Secret Committee members, Little Petar and Little Tux, enjoy playing the board game "Kule" during the breaks between preparing contests and exam revision. The rules of the game assume that the players initially have at their disposal a set of cubes, stacked together to form a tower.

A single turn has Petar splitting the tower into two or more smaller towers, and then ordering these smaller towers in an array. Tux then has to choose one of the smaller towers. This tower will be used for all future turns, while the remainder is discarded. If Tux chooses the kth tower, Petar is obliged to pay k2 dinars to him immediately (e.g. if Tux chose the 3rd tower in the array, Petar has to give him 9 dinars). The game concludes when only a single cube remains.

As it is well-known that Secret Committee members don't have time for anything (including playing games), Petar and Tux decided to, instead of actually playing the game, trust each other that they would have played optimally, and that Petar should immediately give Tux the amount of dinars that he would have won under that condition. They have asked for your help in determining this amount.

Input

The first and only line of the standard input contains a single integer N, the number of cubes in the initial tower.

Output

Write to the first and only line of the standard output a single integer M, representing the amount of dinars that Petar should give to Tux.

Example

Input:
7

Output:
8

Explanation

In one of the possible pair of optimal strategies for Petar and Tux, Petar first splits the tower into two towers of heights 5 and 2 (in that order). Tux chooses the second tower and he immediately gets 4 dinars, after which Petar is forced to split the tower into two towers of heights 1 each. Tux once again chooses the second tower, gaining a total of 8 dinars.

Constraints

  • 2 <= N <= 10100

 


hide comments
vagesh_verma: 2015-07-14 11:28:22

can we do it in this way--
first 7= 4+3 ->1
4=3+1 ->1+1=2
3=2+1 ->2+1=3
2=1+1 ->either 3+1=4 or 3+4=7

Re (PetarV): Not optimal for Tux. If he takes the 2nd tower at the beginning, it would proceed something like this (it's impossible for Petar to get the score under 8 then if Tux plays optimally):

7 = 4 + 3 --> 4
3 = 2 + 1 --> 4 + 1 = 5
2 = 1 + 1 --> 5 + 4 = 9

Last edit: 2015-07-23 04:47:34
Avi Aryan: 2015-07-14 08:59:18

@Akash Goel . But in last one he will choose the 2nd "1" , so his total will be 5 + 2^2 = 9

Akash Goel: 2015-07-13 14:26:54

@PetarV @jkelava6 - shouldn't the optimal answer for test case be 6?
1. 6 1 (choose 6) -> 1
2. 5 1 (choose 5) -> 1+1=2
3. 4 1 (choose 4) -> 2+1=3
4. 3 1 (choose 3) -> 3+1=4
5. 2 1 (choose 2) -> 4+1=5
6. 1 1 (choose 1) -> 5+1=6

Petar can always force the other person to choose 1

Re (PetarV): You're never forced to choose the 1st tower; you can choose the 2nd tower (effectively ending the game).
The strategy you've given is not optimal for Petar. If Tux were to choose the second tower at the end, it would give him 9 points (5 + 2^2) in total.

Last edit: 2015-07-23 04:44:46
jkelava6: 2015-07-02 11:02:27

@Jaswanth taking tower 2 made of 1 cube wouldn't be optimal in that scenario, but taking tower 1 made of 6 cubes!

Jaswanth: 2015-07-01 08:56:58

@PetarV : Why can't we split the Tower with 7 cubes into 6 and 1 and so the answer will be 4 . given " trust each other that they would have played optimally" .
Thanks @jkelava6 got it.

Last edit: 2015-07-02 11:52:06

Added by:PetarV
Date:2015-06-23
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY
Resource:Serbian Olympiad in Informatics 2015 (by Dušan Zdravković)