Description

在一个环形跑道上有N堆石子，每次取相邻两堆进行合并 最终合并成为一堆。请问将每次合并后的代价进行累加 其总和最少为多少

Format

Input

在一个环形跑道上有N堆石子，每次取相邻两堆进行合并最终合并成为一堆。请问将每次合并后的代价进行累加其总和最少为多少

Output

一行，表示最小的总得分

Samples

4
4
5
9
4

43

Limitation

1s, 1024KiB for each test case.