题目描述

操场上有 $n$ 堆石子排成一排，每堆石子都有一定的数量，现要将石子有序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，合并的花费为这两堆石子的总数。石子经过 $n-1$ 次合并后成为一堆。

请编写一个程序，读入堆数 $n$ 及每堆的石子数，并计算合并的最小总花费。

输入格式

第一行一个整数 $n$，表示有 $n$ 堆石子。

第二行 $n$ 个整数，表示每堆石子的数量。

输出格式

输出一行一个整数，表示合并的最小总花费。

样例

3
2 4 5

17

样例解释

合并过程为：先合并第 $1$ 堆和第 $2$ 堆，花费 $2+4=6$，此时石子堆变为 $6,5$；再合并这两堆，花费 $6+5=11$。总花费 $6+11=17$。

数据范围与提示

• $1 \le n \le 100$
• 每堆石子数量为正整数