题目名称：线性石子合并

题目描述：

给定一个长度为 \(n \) 的石子序列，初始时有 \( n \) 堆石子，每一堆有 \( a_i \) 个石子。

每次你可以将相邻的两堆石子合并为一堆，合并的代价为这两堆石子的总数。合并之后，这堆石子仍然可以参与后续合并。

你的任务是通过若干次合并，将所有的石子最终合并成一堆，并求出最小的总合并代价。

输入格式：

• 第一行一个整数 \(n \) \(( 1 \leq n \leq 500 )\)
• 第二行为 \( n \) 个整数 \(a_1, a_2, \ldots, a_n \) 每个 \(( 1 \leq a_i \leq 100 )\)

输出格式：

• 一行一个整数，表示最小的总合并代价。

样例输入：

4
4 5 9 4

样例输出：

44

样例解释：

一种最优的合并方式如下（只展示合并顺序和每次代价）：

• 合并第1堆和第2堆：\(( 4+5=9 )\)，新序列：\([9, 9, 4]\)
• 合并第1堆和第2堆：\(( 9+9=18 )\)，新序列：\([18, 4]\)
• 合并第1堆和第2堆：\(( 18+4=22 )\)，最终合并完毕。

总代价：\(( 9+18+22=49 )\)（本例非最优，仅举例）。