AT_dp_n Slimes

有 $N$ 只史莱姆排成一行。最初，从左到右第 $i$ 只史莱姆的大小为 $a_i$。 太郎君想要将所有史莱姆合成为一只。他会不断重复以下操作，直到只剩下一只史莱姆： - 选择左右相邻的两只史莱姆，将它们合成为一只新的史莱姆。合成前两只史莱姆的大小分别为 $x$ 和 $y$，合成后的史莱姆大小为 $x + y$。此时，太郎君需要支付 $x + y$ 的代价。合成前后，史莱姆们的相对位置不会发生变化。 请你求出太郎君需要支付的总代价的最小值。

输入以如下格式从标准输入读入： > $N$ $a_1$ $a_2$ $\ldots$ $a_N$

输出太郎君需要支付的总代价的最小值。

## 限制条件 - 所有输入均为整数。 - $2 \leq N \leq 400$ - $1 \leq a_i \leq 10^9$ ## 样例解释 1 可以按如下方式进行操作。用粗体表示正在合成的史莱姆。 - (**10**, **20**, 30, 40) → (**30**, 30, 40) - (**30**, **30**, 40) → (**60**, 40) - (**60**, **40**) → (**100**) ## 样例解释 2 例如，可以按如下方式进行操作： - (**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 答案可能无法用 32 位整数型表示。 ## 样例解释 4 例如，可以按如下方式进行操作： - (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**) 由 ChatGPT 4.1 翻译