#J3033. 堆石头

堆石头

题目描述

有n堆不同种类的石头,你需要把所有堆石头合成一堆。每一次合并,你可以把两堆石头合并到一起,消耗的体力等于两堆石头的重量之和。可以看出,所有的石头经过n-1次合并之后,就只剩下一堆了。你在合并石头时总共消耗的体力等于每次合并所耗体力之和。求最小的体力消耗

输入格式

输入包括两行,第一行是一个整数n,表示石头的种类数。

第二行包含n个整数,用空格分隔,第i个整数ai是第i种石头的数目。

输出格式

输出包括一行,这一行只包含一个整数,也就是最小的体力耗费值。
3 
1 2 9 
15

提示

数据约定:
对于100%的数据:

1≤n≤10000,1≤ai≤20000