合并果子

题目描述

在一个果园里，多多已经将所有果子摘了下来，并且按照果子的不同种类分成了若干堆。

现在，多多要把所有果子合并成一堆。

每次合并时，多多可以选择任意两堆果子，将它们合并成一堆。此次合并消耗的体力，等于这两堆果子的重量之和。

经过 (n-1) 次合并后，所有果子会被合并成一堆。

多多合并果子时消耗的总体力，等于每次合并所消耗体力之和。

由于之后还需要把果子搬回家，因此多多希望采用一种合并顺序，使消耗的总体力尽可能小。

假设每个果子的重量均为 (1)。已知果子的种类数以及每种果子的数量，请计算将所有果子合并成一堆所需要的最小体力。

示例说明

假设有 (3) 堆果子，数量分别为：

1 2 9

可以先合并数量为 (1) 和 (2) 的两堆果子：

1 + 2 = 3

本次消耗体力为：

3

此时剩下两堆果子：

3 9

再将这两堆果子合并：

3 + 9 = 12

本次消耗体力为：

12

因此消耗的总体力为：

3 + 12 = 15

可以证明，(15) 是最小的体力消耗值。

输入格式

输入共两行。

第一行输入一个整数 (n)，表示果子的种类数。

第二行输入 (n) 个整数 (a_1,a_2,\ldots,a_n)，其中 (a_i) 表示第 (i) 种果子的数量。

输出格式

输出一个整数，表示将所有果子合并成一堆所需要的最小体力。

输入数据保证答案小于 (2^{31})。

数据范围

1 ≤ n ≤ 10000
1 ≤ ai ≤ 20000

对于不同规模的数据：

30% 的数据满足 n ≤ 1000
50% 的数据满足 n ≤ 5000
100% 的数据满足 n ≤ 10000

样例输入

3
1 2 9

样例输出

15