Problem B: 木匠PIPIⅢ

Problem B: 木匠PIPIⅢ

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 76  Solved: 14
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI现在又成了一名木匠,接一些切木头的活。
顾客会给PIPI一根长度为m的木棍,要求PIPI把它切成一些固定长度的小木棍,但是每次切割以要切成的两根木块中较长的那块的长度为代价。
例如一根长为10的木棍,想要切成长度为3和7的木棍,代价就是7,现在请你帮PIPI制定切割方案以获得最小的代价~输出最小代价即可~

Input

多组输入。
第一行输入要切成的小木棍的数量n(1<=n<=1e4)。
接下来输入n个正整数,代表顾客要求得到的小木棍长度,所有小木棍长度之和即为原木棍的长度,原木棍的长度不超过1e9。

Output

输出最小代价。

Sample Input

3
2 3 5

Sample Output

8