合并果子

题目描述

Orange有 $n$ 堆果子，其中第 $i$ 堆果子有 $a_i$ 个，每次他可以从这些果子中任意挑选 $2$ 堆，记为 $x$ 和 $y$，将他们合并成一堆大的果子，这将消耗Orange $x + y$个单位的体力。现在Orange想要用最少的体力将所有的果子合并成一堆，请问你Orange最小的体力花费为多少？

输入格式

输入共2行，第一行为整数 $n(n \leq 10^5)$，第二行包含 $n$ 个整数 $a_i(a_i \leq 10^9)。$

输出格式

一个整数，表示Orange最小花费的体力。

样例 #1

样例输入 #1

3
2 1 9

样例输出 #1

15

提示

Orange可以先合并 $1 + 2$，花费3体力，果子变为 $3 9$。

然后合并 $3 + 9$，花费12;果子变为15。

完成上述操作共花费$3 + 12 = 15$单位的体力。