最大运输费用货物储运问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

在一个铁路沿线顺序存放着n堆装满货物的集装箱。货物储运公司要将集装箱有次序地集中成一堆。规定每次只能选相邻的2 堆集装箱合并成新的一堆,所需的运输费用与新的一堆中集装箱数成正比。 给定各堆的集装箱数,试确定使总运输费用最大的运输方案。
设n堆货物从左到右编号为1,2,…,n。各堆货物集装箱数为a[1:n]。
对于给定n堆货物,计算合并成一堆的最大运输费用。

Input

输入数据的第1 行是正整数n(n≤5000),表示有n堆货物。第2 行有n个数,分别表示每堆货物的集装箱数。

Output

将计算出的最大运输费用输出。

Sample Input

4
4 4 5 9

Sample Output

43

Hint

Source