附加文件

题目描述

有 $n$ 堆石子，第 $i$ 堆石子的重量为 $w_i$。现要将所有石子合并成一堆。每一次合并，可以任选两堆石子合并成一堆，消耗的体力等于这两堆石子的重量之和。消耗的总体力等于每次合并所耗体力之和。

问：如何合并，可使得消耗的总体力最小？你只需要输出消耗的最小总体力。

输入格式

第一行：一个整数 $n$

第二行：$n$ 个整数$w_i$。

输出格式

一个整数，表示答案。

样例输入

3 
1 2 6

样例输出

12

样例解释

先将 1 和 2 合并，消耗 3 体力。得到新的一堆 3。

再将 3 和 6 合并，消耗 9 体力。至此全部合成为一堆。

共计消耗 12 体力。

数据规模

共 $12$ 个测试点，全部数据保证 $1 ≤ n ≤ 10^7$， $1 ≤ w_i ≤ 10^5$。

测试点 1-10（共40分）：

• $测试点 1-3，保证有 n ≤ 1000；$

• $测试点 4-5，保证有 n ≤ 5000；$

• $测试点 6-10，保证有 n = 10000。$

测试点 11-12（共60分）：

• $测试点 11-12，保证有 n ≤ 10^7。$