80. 石子合并

【题目描述】

设有$N$堆石子排成一排，其编号为$1,2,3,…,n(n<=100)$。每堆沙子有一定的数量。现要将$N$堆沙子并成为一堆。归并的过程只能每次将相邻的两堆沙子堆成一堆（每次合并花费的代价为当前两堆沙子的总数量），这样经过$N-1$次归并后成为一堆，归并的总代价为每次合并花费的代价和。找出一种合理的归并方法，使总的代价最小。

例如：有$3$堆沙子，数量分别为$13,7,8$，有两种合并方案:

第一种方案：先合并$1,2$号堆，合并后的新堆沙子数量为$20$，本次合并代价为$20$，再拿新堆与第$3$堆沙子合并，合并后的沙子数量为$28$，本次合并代价为$28$，将$3$堆沙子合并到一起的总代价为第一次合并代价$20$加上第二次合并代价$28$，即$48$；

第二种方案：先合并$2,3$号堆，合并后的新堆沙子数量为$15$，本次合并代价为$15$，再拿新堆与第$1$堆沙子合并，合并后的沙子数量为$28$，本次合并代价为$28$，将$3$堆沙子合并到一起的总代价为第一次合并代价$15$加上第二次合并代价$28$，即$43$；

采用第二种方案可取得最小总代价，值为$43$。

【输入格式】

输入由若干行组成，第一行有一个整数$n（1≤n≤100）$；表示沙子堆数。第$2$至$n+1$行是每堆沙子的数量。 

【输出格式】

一个整数，归并的最小代价。

【输入样例】

7
13
7
8
16
21
4
18

【输出样例】

239