Description

今天课间的时候，小明同学在学校的操场上发现了n堆大小不一的小石子，小明决定将它们合并成一堆,但现在小明思考着这样一个问题：如何消耗最少的体力，把这n堆小石子合并成一堆？现已知合并所消耗的体力等于每次合并两堆小石子的重量之和,每次合并，他会把其中的两堆小石子合并到一起，n堆小石子经过n-1次合并之后就只剩一堆了。

比如，n=3时表示共有3堆，每堆重量分别是2、1、9。一种合并方案是2和9 合并，新堆重量是11，耗费体力为11;接着11与1合并，新堆重量是12,耗费体力为12, 因此总消耗体力是11+12=23。另一种方案是1和2合并，新堆重量是3,耗费体力为3, 接着3和9合并，新堆重量是12，耗费体力为12，因此总消耗体力是3+12=15。可以证明 这样合并就是最少耗费体力的方法。

Input Format

3
2 1 9

15

Source