说明

有n堆石子围成一个圆圈。现在需要把它们合并成一堆石子。每次合并时，只能合并相邻的两堆石子，所耗力气为两堆石子重量之和，合并得到的新堆的重量为原两堆重量之和。问最少需要耗费多少力气？ 数据规模：1<=n<=200，合并n堆石子最少需要耗费的力气不超过2*10^9。

输入格式

第一行一个整数n，第二行n个整数，表示顺序排列的每堆石子的重量。

输出格式

只有一行，该行只有一个整数，表示合并这n堆石子最少需要耗费的力气。

样例

3
1 3 5

13