Background

小灿在被做成食品之前，重情重义的刘宝宝早就赶到了机器所在地旁边的山的山峰上，现在山峰上有许多的石子排成了1排（不要在乎为什么山峰上可以有一排石子），他们的重量都为1，刘宝宝很懒，他只会把相邻的石子合并在一起，已知合并石子的要耗费刘宝宝石子重量和的体力，还是因为刘宝宝很懒，所以刘宝宝只会耗费最小的体力来合并所有的石子，又是因为刘宝宝很懒，他想让你来算算这个消耗的体力值。当然最后推石头下山是你来推hahaha。

Description

有n个石头排成一排，第i个重量为1,每次可以合并相邻两堆石子，需要的体力为两堆重量之和，新的一堆石子的重量也为两堆石子的重量和,求：将这n个石子合并为一堆需要的体力和的最小值。

Input

一个数n，表示有n个石子

Output

一个数ans，表示最少的体力消耗
了防止因为答案太大从而爆int/long long, 请大家使用unsigned long long 数据类型，
采取自然溢出的方法对2^64取膜(自然溢出就是你不需要取膜)。

Sample 1

Input

4

Output

8

Limitation

1000ms, 512MB

Hint

5% n<=5
30% n<=100
45% n<=2333
60% n<=100000
100% n<=10^15

后记

小灿被刘宝宝救出后，小铭感到自己队友的弱小，他决定自己来迎战刘宝宝，刘宝宝带了