1434: 自动打包机*

Memory Limit：400 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：64 Solved：25

Description

       有若干堆货物排成一行，每堆都有一定的重量。有一个打包机，每次可以将相邻的两堆货物合并成一堆，合并需要消耗的能量为两堆货物的重量和。合并后，两堆货物仍然保持原来的前后位置。计算将所有货物合并成一堆所需要消耗的最少能量。

      例如，有4堆货物，分别重13, 7, 14, 6，


      那么打包消耗的能量如下图所示：
tle="" align="" />


tle="" align="" />

可见，合理地合并能够减少能量的消耗。

请编写程序，输入货物数量和每堆的重量，输出完成打包所需要消耗的最少能量。


Input

输入分两行。
第一行为货物的堆数n，第二行为n个正整数，表示每一堆货物的重量。

Output

输出完成打包所需的最少能量。

Sample Input Copy 

4
13 7 14 6

Sample Output Copy 

80

HINT

货物不超过n堆，1<=n<=10000。
每堆货物的重量为整数，且消耗的能量不会超过整数范围。