题目描述

在操场上从左到右摆放着N堆石子。每次只能选择相邻的两堆合并成一堆，本次得分等于合并后这堆石子的数量。

请将所有石子合并成一堆，使各次得分之和最小。石子排列成一行，不是首尾相连的环。

输入格式

第一行一个整数N。接下来N行，每行一个整数，依次表示各堆石子的数量。

输出格式

输出最小总得分。

样例

7
13
7
8
16
21
4
18

239

数据范围

2≤N≤100；每堆石子数量为正整数，且小于10000。