题目描述

小码哥有$n$堆果子，第$i$堆果子有$a_i$个果子。小码哥要将所有的果子合并为一堆。

小码哥一次只能将两堆果子合并为一堆，消耗的体力是这两堆果子个数之和。容易看出，$n-1$次合并之后，所有的果子被合并为一堆。

小码哥很懒，他希望自己耗费的体力尽可能小，你能告诉他这个最小的体力耗费值吗？

输入格式

第一行输入一个整数$n$。 第二行输入$n$个整数$a_i$。

输出格式

输出一行一个整数，表示你的答案。

样例输入 #1

3
1 2 4

样例输出 #1

10

说明/提示

对于20%的数据，有$1\leq n\leq 10$。 对于另外40%的数据，有$1\leq n\leq 1000$。 对于100%的数据，有$1\leq n\leq 10^5,1\leq a_i\leq 10^5$。