该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

秋天到了，果园里有许多堆果子需要合并成一堆运走。每次合并两堆果子需要消耗的体力等于这两堆果子的重量之和。农民小王想知道，如何合并才能使消耗的总体力最少。

题目描述

果园里有 $n$ 堆果子，每堆果子有一个重量 $a_i$。每次可以选择任意两堆果子合并成一堆，合并的代价等于这两堆果子的重量之和。

请计算将所有果子合并成一堆所需要的最小总代价。

输入格式

第一行包含一个正整数 $n$（$1 \le n \le 10^4$），表示果子的堆数。

第二行包含 $n$ 个正整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^4$），表示每堆果子的重量。

输出格式

输出一个整数，表示最小总代价。如果只有一堆果子，输出 $0$。

样例

3
1 2 9

15

5
7 8 4 6 1

57