1744: 石子合并问题

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：32 Solved：16

Description

     堆料场上有N(N≤1000) 堆石子排成一排。现在要将这N 堆石子合并成为一堆。每次只能合并相邻的两堆，合并后与这两堆石子相邻的石子将和新堆相邻。合并两堆石子所花费的时间为两堆石子的数量和。求将N堆石子合并成一堆最小花费的时间。

Input

输入第一行一个整数 N。第二行 N个正整数表示每一堆石子的数量 (1=< 数量<=100 ），数字间空一格。

Output

输出一个正整数，为石子合并成一堆的最小花费时间。

Sample Input Copy 

4 
4 2 3 4

Sample Output Copy 

26

HINT

2=<N<=1000; 1=<石子数量<=100