题目描述

有一个任务是将$\red{n}$个人集合起来，但每个人都有一个懒散值。已知一次可以将两群人集合在一起，所花费的体力是这两堆人的懒散值之和。可以看出，经过$\red{n－1}$次集合，所有的人就集合在一起了。例如有$\red{3}$个人，懒散值依次为$\red{1，2，9}$。可以先将懒散值为$\red{1、2}$的合并为一群，新群数目为$\red{3}$，耗费体力为$\red{3}$。接着，将新群与懒散值为$\red{9}$的合并，又得到新的群，数目为$\red{12}$，耗费体力为$\red{12}$。所以总共耗费体力$\red{＝3＋12＝15}$。可以证明$\red{15}$为最小的体力耗费值。那么，怎样集合，花费的体力最少呢？

输入格式

输入数据包括两行，第一行是一个整数$\red{n（1≤n≤10 000）}$，表示人数。第二行包含$\red{n}$个整数，用空格分隔，第$\red{i}$个整数$\red{a_i（1≤a_i≤20 000）}$是第$\red{i}$个人的懒散值。

输出格式

输出一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于$\red{2^{31}}$。

样例

输入样例

3

1 2 9

输出样例

15

提示

对于$\red{30\%}$的数据，保证有$\red{n≤1 000：}$

对于$\red{50\%}$的数据，保证有$\red{n≤5 000；}$

对于全部的数据，保证有$\red{n≤10 000}$。