T376874 石子合并

设有 $n$ 堆石子排成一圈，其编号为 $1,2,3,\cdots,n$。每堆石子有一定的质量 $a_i\ $。现在要将这 $n$ 堆石子合并成为一堆。每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻。合并时由于选择的顺序不同，合并的总代价也不相同。试找出一种合理的方法，使总的代价最大，并输出最大代价。

第一行一个整数，表示$n$ 第二行$n$个整数，表示$a_i$

输出一行一个答案

对于$70\%$的数据：$1\leq n\leq 300$ 对于$100\%$的数据：$1\leq n\leq 3000,1\leq a_i\leq 100$