Description

有 $N$ 个光头排成一排。最初，从左边起第 $i$ 个光头的大小为 $a_i$。

光头强正试图将所有的光头混合成更大的光头。他将重复执行以下操作，直到只有一个光头：

选择两个相邻的光头，并将它们组合成一个新的光头。新的光头的大小为 $x+y$，其中 $x$ 和 $y$ 是光头在合并之前的大小。在这里，产生了 $x+y$ 的费用。组合光头时，光头的位置关系不会改变。

输出最小的可能的总费用。

Input

输入格式如下：

$N\\a_1\ a_2…a_N$

输入中的所有值都是整数。

$2≤N≤400\\1≤a_i≤10^9$

Output

输出最小的可能的总费用。

Samples

4
10 20 30 40

190

光头强的做法如下：

$(10, 20, 30, 40) → (30, 30, 40)$

$(30, 30, 40) → (60, 40)$

$(60, 40) → (100)$

5
10 10 10 10 10

120

光头强应该这样做：

$(10, 10, 10, 10, 10) → (20, 10, 10, 10)$

$(20, 10, 10, 10) → (20, 20, 10)$

$(20, 20, 10) → (20, 30)$

$(20, 30) → (50)$

3
1000000000 1000000000 1000000000

5000000000

答案可能超过32位整数类型。

6
7 6 8 6 1 1

68

光头强应该这样做：

$(7, 6, 8, 6, 1, 1) → (7, 6, 8, 6, 2)$

$(7, 6, 8, 6, 2) → (7, 6, 8, 8)$

$(7, 6, 8, 8) → (13, 8, 8)$

$(13, 8, 8) → (13, 16)$

$(13, 16) → (29)$