题目描述

桌面上从左到右放着 $n(1 \le n \le 200)$ 堆石子，其中第 $i$ 堆石子包含的石子数量为 $a_i$ 。
现在要将石子有序地合并成一堆。
规定每次只能取相邻的两堆石子合并成新的一堆，并将新的一堆的石子数，记为该次合并的花费。
那么，$n−1$ 次合并后，石子将合并成一堆。
你需要寻找一种合并方案，使得花费总和最小。输出最小的花费总和。

输入格式

输入的第一行包含一个整数 $n(1 \le n \le 200)$，用于表示石子堆数。
输入的第二行包含 $n$ 个整数，以空格间隔，分别表示初始时每一堆的石子数。

输出格式

输出一个整数，用于表示将 $n$ 堆石子合并成一堆的最小花费。

5
1 3 2 4 5

34