2090: 宝典2第五章紧急集合

【题目描述】紧急集合（fruit.cpp/c/pas）NOIP2004合并果子

史上著名的大魔导师列别捷夫曾经说过：“平静的湖面，锻炼不出精悍的水手；安逸的生活打造不出时代的伟人。”这句话用在监狱的狱警身上实在是再恰当不过，由于监狱一千年来从未出过任何差错，因此几乎所有的狱警都或多或少的有些懒散，我们可以将之量化为一个数值即懒散值。所以当典狱长决定集合n个狱警以围捕修罗王和邪狼时，他所花费的体力是可观的。

典狱长一次可以将两群人集合在一起，所花费的体力是这两堆人的懒散值之和。可以看出，经过n－1次集合，所有的狱警就集合在一起了。例如有3个狱警，懒散值依次为1，2，9。可以先将懒散值为1、2的狱警合并为一群，新群数目为3，耗费体力为3。接着，将新群与懒散值为９的狱警合并，又得到新的群，数目为12，耗费体力为12。所以典狱长总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。那么，怎样集合，典狱长花费的体力最少呢？　

【输入文件】

输入文件fruit.in包括两行，第一行是一个整数n(1≤n≤10000)，表示狱警人数。第二行包含n个整数，用空格分隔，第i个整数a_i(1≤a_i≤20000)是第i个狱警的懒散值。

【输出文件】

输出文件fruit.out包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于2³¹。

【样例输入】

3

1 2 9

【样例输出】

15

【数据规模】

对于30％的数据，保证有n≤1000：

对于50％的数据，保证有n≤5000；

对于全部的数据，保证有n≤10000。