Migrated from Lutece 886 方老师金币堆

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

虽然方老师赚到了很多钱，但是有些钱却非常难处理，经常会有人会以一大袋金币的方式来支付方老师的演讲报酬。现在方老师家里已经放置了$N$袋金币了，每一袋金币质量为$A_i$，他想把这些金币合并在一袋里面，然后存到银行去，于是方老师把这$N$袋金币围成一个圈，每一次他可以把相邻两袋金币合并，并消耗两袋金币质量总和的体力，他想让你帮他算下，他最少消耗多少体力可以完成这项工作。

注意：开始时第$i$袋金币与第$i+1$袋金币相邻，第$1$袋金币与第$N$袋金币相邻。

Input

输入有多组数据

每组数据第一行有$1$个正整数$N$,表示有$N$袋金币$(1 \leq N \leq 100)$

每组数据第二行$N$个整数，第$i$个整数表示第$i$袋金币的质量为$A_i(1\leq A_i \leq 50)$

Output

输出$1$个整数，表示方老师最少消耗的体力。

Samples

4
1 1 1 1

8

Resources

2014 UESTC Training for Dynamic Programming