U461930 石子合并

给定 $N$ 堆石子，编号为 $1, 2, 3, ..., N$，并且每堆石子有一定的质量。我们需要将这 $N$ 堆石子合并成一堆，每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和。 我们的目标是找出一种合理的方法，使得总的合并代价最小。 例如，假设有 $4$ 堆石子分别为 $1, 3, 5, 2$。我们可以按照以下步骤进行合并： 1. 合并第一堆和第二堆，代价为 $1 + 3 = 4$，得到 $4, 5, 2$。 2. 合并第一堆和第二堆，代价为 $4 + 5 = 9$，得到 $9, 2$。 3. 合并第一堆和第二堆，代价为 $9 + 2 = 11$，最终得到 $11$。 总的合并代价为 $4 + 9 + 11 = 24$。 如果第二步是先合并第 $2$ 堆和第 $3$ 堆，合并代价为 $7$，得到 $4\ 7$，最后一次合并代价为 $11$，总代价为 $4 + 7 + 11 = 22$。 因此，我们需要找到一种最优的合并顺序，使得总的合并代价最小，并输出最小代价。

第一行一个整数 $N(1 \leq N \leq 300)$，表示石子的堆数。 第二行包含 $N$ 个整数 $a_i(1 \leq a_i \leq 1000)$，表示每堆石子的质量。

输出一个整数，表示最小代价。