题目描述

Huffman树在编码中有着广泛的应用。在这里，我们只关心Huffman树的构造过程。 给出一列数 $p_i​=p_0,p_1,…,p_{n−1}$，用这列数构造Huffman树的过程如下：
1.找到 pi​ 中最小的两个数，设为 pa​ 和 pb​，将 pa​ 和 pb​ 从 pi​ 中删除掉，然后将它们的和加入到 pi​ 中。这个过程的费用记为pa​ + pb​。
2.重复步骤 1，直到 pi​ 中只剩下一个数。 在上面的操作过程中，把所有的费用相加，就得到了构造Huffman树的总费用。 本题任务：对于给定的一个数列，现在请你求出用该数列构造Huffman树的总费用。 例如，对于数列 pi​=5,3,8,2,9，Huffman树的构造过程如下：
1.找到 5,3,8,2,9 中最小的两个数，分别是 2 和 3，从 pi​ 中删除它们并将和 5 加入，得到 5,8,9,5，费用为 5。
2.找到 5,8,9,5 中最小的两个数，分别是 5 和 5，从 pi​中删除它们并将和 10 加入，得到 8,9,10，费用为 10。
3.找到 8,9,10 中最小的两个数，分别是 8 和 9，从 pi​ 中删除它们并将和 17 加入，得到 10,17，费用为 17。
4.找到 10,17 中最小的两个数，分别是 10 和 17，从 pi​中删除它们并将和 27 加入，得到 27，费用为 27。
5.现在，数列中只剩下一个数 27，构造过程结束，总费用为 5+10+17+27=59。

输入描述

输入的第一行包含一个正整数 n。 接下来是 n 个正整数，表示 $p_0,p_1,…,p_n−1$，每个数不超过 1000。

输出描述

输出用这些数构造 Huffman 树的总费用。

5
5 3 8 2 9

59

提示

数据范围与提示

n≤100