在一个果园里，达达已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。

达达决定把所有的果子合成一堆。

每一次合并，达达可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。

可以看出，所有的果子经过 $n-1$ 次合并之后，就只剩下一堆了。

达达在合并果子时总共消耗的体力等于每次合并所耗体力之和。

因为还要花大力气把这些果子搬回家，所以达达在合并果子时要尽可能地节省体力。

假定每个果子重量都为 $1$，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使达达耗费的体力最少，并输出这个最小的体力耗费值。

例如有 $3$ 种果子，数目依次为 $1，2，9$。

可以先将 $1、2$ 堆合并，新堆数目为 $3$，耗费体力为 $3$。

接着，将新堆与原先的第三堆合并，又得到新的堆，数目为 $12$，耗费体力为 $12$。

所以达达总共耗费体力$\=3+12=15$。

可以证明 $15$ 为最小的体力耗费值。

输入格式

输入包括两行，第一行是一个整数 $n$，表示果子的种类数。

第二行包含 $n$ 个整数，用空格分隔，第 $i$ 个整数 $a_i$ 是第 $i$ 种果子的数目。

输出格式

输出包括一行，这一行只包含一个整数，也就是最小的体力耗费值。

输入数据保证这个值小于 $2^{31}$。

数据范围

$1 \le n \le 10000$,
$1 \le a_i \le 20000$

输入样例：

3 
1 2 9 

输出样例：

15

下面按 k=1..25 说明这套“合并果子（最小体力=每次合并两堆代价之和）”数据分别在卡哪些常见错误做法。 （正确解法：每次取当前最小的两堆合并，用小根堆/Huffman。）

1. 样例 [1,2,9]：基础正确性。
2. n=1：答案应为 0；卡有人输出该堆重量或进行一次合并。
3. n=2：答案就是两数之和；卡边界处理/循环条件写错。
4. 全 1（5 个）：卡“合并顺序随便都一样”的误解；也卡实现里漏加某次代价。
5. 递增小数组：综合正确性；卡把输入顺序当合并顺序（不取最小两堆）。
6. 递减（与 5 同 multiset）：卡对“输入顺序不应影响答案”的错误实现（答案必须与 5 相同）。
7. 全最大值（三个 20000）：卡 int16/short 溢出、以及大数相加类型问题。
8. 一个极大 + 多个极小：卡错误贪心（比如先合并大堆）、以及堆维护错误。
9. 大量重复值（20 个 2）：卡性能/堆操作、以及重复值处理（有些人错误去重）。
10. 素数序列：综合正确性（分布不规则），卡写死策略/排序一次后相邻合并等错法。
11. 2 的幂：数值跨度大，卡错误策略（如“总合并最接近的/按位”之类奇怪 heuristics）。
12. 大小交替：卡“先排序一次然后固定相邻合并”会错；也卡没用动态结构导致出错。
13. 小范围随机（30 个）：综合正确性，卡各种隐蔽 bug。
14. 专卡“排序一次后合并相邻”错误 [1,2,10,11]：正确 Huffman 与“先(10+11)”这类相邻合并会产生明显差异。
15. 另一个相邻合并陷阱 [1,1,8,9,10]：继续卡“只排序一次/按相邻合并/不重新插回再取最小两堆”。
16. n=1000 随机大范围：卡时间复杂度（O(n^2) 反复找最小会慢），也卡堆实现稳定性。
17. n=10000 全 1（压力）：强卡性能（必须 O(n log n)），也卡输出用 int 但中间累计可能大（需要至少 32-bit，很多语言用 int 够但别用 short）。
18. n=10000 全 20000（压力+大数）：强卡性能 + 累计代价很大，卡 32-bit/溢出（虽然题目保证 <2^31，但中间若用更小类型会炸）。
19. n=10000 递增序列（1..）：卡“以为数据有序就能用特殊规律/双指针”但写错；也卡堆/优先队列实现 bug。
20. n=9999 小范围随机（1..100）：强卡性能（很多重复），也卡数组/堆边界（非 2 的幂长度）。
21. n=10000：1 与 20000 的混合（稀疏大值）：卡错误贪心（先合并大堆）、以及堆中大量相同小值时的稳定性。
22. n=10000：20000 与 19999 各 5000（大数+重复）：卡溢出/类型；也卡某些“压缩计数后合并”写错（频次处理不当）。
23. 专卡“用大根堆/每次取最大两堆”错误 [1,2,3]：最大优先会得到更大代价。
24. 经典样例 [4,3,2,6]（答案 29）：卡多种错法（如相邻合并、先合并大堆等），是 Huffman 常用检验点。
25. n=5000 随机大范围：综合中大规模正确性与性能，卡实现细节（堆 push/pop、long long/int）。

如果你还想更狠地卡某类错误（比如：用排序数组+指针但没处理“新堆插回”的那种、或忘记把合并后的堆再放回集合），我可以再加几组专门针对这些 bug 的小用例。