在一个果园里,有 堆果子。lyy 决定把所有的果子合成一堆。
每一次合并,lyy 可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和。lyy 在合并果子时总共消耗的体力等于每次合并所耗体力之和。
假定每个果子重量都为 ,给定每堆果子的数目,你的任务是设计出合并的次序方案,使 lyy 耗费的体力最少,并输出这个最小的体力耗费值。
输入
第一行是一个整数 ,表示果子的堆数。
第二行包含 个整数,用空格分隔,第 个整数 是第 种果子的数目。
输出
一个整数,也就是最小的体力耗费值。
样例
标准输入 复制文本 |
3 1 2 9 |
标准输出 复制文本 |
15 |