3021 - 石子合并

通过次数

12

提交次数

37

时间限制 : 1 秒
内存限制 : 128 MB

有n堆石子,现要将石子合并成一堆。每次只能移动相邻的2堆石子合并,合并花费为新合成的一堆石子的数量。求将这n堆石子合并成一堆的总花费最小。

输入

第1行为石子堆数n。 第2行为n个数,表示每堆石子数,每两个数之间用一个空格分隔。

输出

将石子合并为一堆的最小花费。

样例

输入

4
4 5 9 4

输出

43

来源

动规专题