合并果子

题目描述

有 n 堆果子，第 i 堆有 a_i 个。每次可以选择两堆合并为一堆，消耗体力等于这两堆果子数量之和。重复进行直到只剩一堆。请你设计合并顺序，使总消耗的体力最小，并输出该最小值。

输入格式

• 第一行：一个整数 n（1 ≤ n ≤ 1000）。
• 第二行：n 个整数 a_1, a_2, …, a_n（1 ≤ a_i ≤ 1000）。

输出格式

• 一行一个整数，表示最小总消耗体力。

输入输出样例 #1

输入 #1

3
1 2 9

输出 #1

15

说明/提示

• 数据规模 n ≤ 1000，a_i ≤ 1000。