AT_kupc2012_10 刺身

狐狸しえる在河边钓鱼。钓到了一条又黑又细长的鱼，于是决定当场把它切成片做成生鱼片吃。 鱼的体长为 $N$ 厘米。奇怪的是，这条鱼身体的各个部分密度不同。把鱼的身体从头部开始每 $1$ 厘米划分一段并依次编号为 $1、2、……、N$ 时，身体第 $i$ 部分的重量为 $w [i]$。把鱼的第 $i$ 部分到第 $j$ 部分表示为 $[i..j]$。最初，可以认为しえる只拿着一张鱼的身体 $[0..N - 1]$。しえる想要把它切开，最终得到被分割成 N 个的鱼的身体 $[0..0],[1..1],...,[N - 1..N - 1]$。 しえる现在在野外，没有砧板之类的东西，所以决定用一种杂技般的方法来切鱼的身体：首先，拿起一张鱼的身体，把它表示为 $[i..j]$。这条鱼的身体长度必须至少为 $2$ 厘米以上，即 $j - i ≥ 1$。接着，把它抛向空中。然后手持日本刀，把在空中飞舞的鱼切成两半。此时，しえる凭借强壮的运动神经可以在任意位置切开这条鱼，但必须在 $1$ 厘米划分的位置切开。这样，原来鱼的身体 $[i..j]$ 就会根据任意的切断位置 $k(i ≤ k < j)$，被分割成 $[i..k]$ 和 $[k + 1..j]$ 两部分。用这种杂技般的方法把鱼的身体切成两部分时，会花费与原来身体重量相等的成本（即$ w [i]+w [i + 1]+...+w [j]$）。 しえる想要把鱼的所有部分切成 $1$ 厘米长的小段，并且使花费的总成本总和最小。

``` N w1 w2... wN ``` $N$ 是鱼的体长。 $w_{i}$ 是鱼的第 $i$ 部分的重量。

请输出将鱼切成 $N$ 个部分所花费的总成本的最小值。 **输入输出样例** #1输入 ``` 3 1 2 3 ``` #1输出 ``` 9 ``` #2输入 ``` 6 9876543210 9876543210 9876543210 9876543210 9876543210 9876543210 ``` #2输出 ``` 158024691360 ``` #3输入 ``` 10 127 131 137 139 149 151 157 163 167 173 ``` #3输出 ``` 5016 ```

输入值全都是整数。 对于 $30\%$的数据： $2≤N≤100,1≤w_{i}≤10^{10}$。 对于 $100\%$的数据： $2≤N≤4000,1≤w_{i}≤10^{10}$。