题目描述

在一个果园里，多多将果子按种类分成不同的堆。他每次可以合并两堆果子，消耗的体力等于两堆果子的重量之和。目标是通过 $n-1$ 次合并将所有果子合成一堆，并使得总体力消耗最小。

输入格式

第一行一个整数 $n$，表示果子的种类数（即堆数）。
第二行 $n$ 个整数，表示每堆果子的数目。

输出格式

一行，一个整数，表示最小的体力耗费值。

3
1 2 9

15

提示

样例 1 说明

有 $3$ 种果子，数目依次为 $1$，$2$，$9$。

• 可以先将 $1$、$2$ 堆合并，新堆数目为 $3$，耗费体力为 $3$。
• 接着，将新堆与原先的第三堆合并，得到新的堆，数目为 $12$，耗费体力为 $12$。
• 总共耗费体力 $= 3 + 12 = 15$。
  可以证明 $15$ 为最小的体力耗费值。

数据规模与约定

对于全部的测试点，保证 $1 \leq n \leq 10 ^ 4$，$1 \leq a_i \leq 2 \times 10 ^ 4$，且答案小于 $2^{31}$。

本题改编自 NOIP 2004 提高组