题目描述

在操场上沿一直线排列着 $n$ 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的两堆石子合并成新的一堆， 并将新的一堆石子数记为该次合并的得分。允许在第一次合并前对调一次相邻两堆石子的次序。

计算在上述条件下将 $n$ 堆石子合并成一堆的最小得分。

输入格式

输入数据共有二行。第 $1$ 行是石子堆数；第 $2$ 行是顺序排列的各堆石子数，每两个数之间用空格分隔。

输出格式

输出合并的最小得分。

3
2 5 1

11

5
10 3 5 6 8

72

数据规模与约定

$n\le200$，各堆石子数 $\le 20$。

提示

此题用贪心是错误的。