问题 Z: 石子合并
内存限制：128 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：568
解决：128
题目描述
在一个操场上摆放着一排n（n≤1000）堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的体力花费。试编程求出将n堆石子合并成一堆的最小花费。例如有3堆石子，数目依次为1，2，9。可以先将 1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为 12。所以总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。
输入
输入包括两行，第一行是一个整数n（1 <= n <= 1000），表示石子的种类数。第二行包含n个整数，用空格分隔，第i个整数ai（1 <= ai <= 100）是第i堆石子的数目。
输出
输出包括一行，这一行只包含一个整数，也就是最小的体力耗费值。
样例输入 复制
3
1 2 9样例输出 复制
15