问题陈述

有 $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$

输出

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

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)

来源

https://atcoder.jp/contests/dp/tasks/dp_n