T4 合并石子（merge）

题目描述

有 $n$ 堆石子排成一行，第 $i$ 堆石子有 $a_i$ 个。每次只能把相邻的两堆石子合并成一堆，合并的代价等于这两堆石子的石子总数（新堆的石子数即为两者之和）。

例如有三堆 $1,2,3$：若先合并前两堆得到代价 $3$，石子变为 $3,3$，再合并代价 $6$，总代价 $9$；若先合并后两堆得到代价 $5$，石子变为 $1,5$，再合并代价 $6$，总代价 $11$。

请你把所有石子合并成一堆，求最小总代价。

输入文件为 merge.in，输出文件为 merge.out。

输入格式

第一行一个正整数 $n$，表示石子堆数。

第二行 $n$ 个正整数 $a_1,a_2,\dots,a_n$，表示每堆石子的数量。

输出格式

一行一个整数，表示最小总代价。

样例 1 输入

4
1 3 5 2

样例 1 输出

22

样例 1 解释

一种最优方案是：先合并第 $3,4$ 堆 $5+2=7$，石子变为 $1,3,7$；再合并第 $1,2$ 堆 $1+3=4$，石子变为 $4,7$；最后合并 $4+7=11$。总代价 $7+4+11=22$。

数据规模与约定

• 对于 $30\%$ 的数据，保证 $n \le 10$。
• 对于 $100\%$ 的数据，保证 $1 \le n \le 300$，$1 \le a_i \le 100$。