A54979.史莱姆

有 $N$ 个史莱姆排成一排。最初，第 $i$ 个史莱姆的大小是 $a_i$ 。

太郎正试图将所有的史莱姆组合成一个更大的史莱姆。他会反复执行下面的操作，直到只有一个史莱姆为止：

• 选择两个相邻的史莱姆，将它们组合成一个新史莱姆。新史莱姆的大小为 $x + y$ ，其中 $x$ 和 $y$ 是组合前史莱姆的大小。这里需要花费 $x + y$ 。在组合史莱姆时，史莱姆的位置关系不会改变。

求可能产生的最小总成本。

限制因素

• 所有输入值均为整数。
• $2 \leq N \leq 400$
• $1 \leq a_i \leq 10^9$

输入内容由标准输入法提供，格式如下：

$N$
$a_1$ $a_2$ $\ldots$ $a_N$

打印可能产生的最低总成本。

样本 1 解释

太郎应该做的事情如下（粗体字显示的是正在组合的粘液）：

• (10, 20, 30, 40) → (30, 30, 40)
• (30, 30, 40) → (60, 40)
• (60, 40) → (100)