题目描述

问题描述

基础练习 Huffman 树。
时间限制：1.0s 内存限制：512.0MB。

Huffman 树在编码中有着广泛的应用。在这里，我们只关心 Huffman 树的构造过程。

给出一列数 $\{p_i\} = \{p_0, p_1, \dots, p_{n-1}\}$，用这列数构造 Huffman 树的过程如下：

1. 找到 $\{p_i\}$ 中最小的两个数，设为 $p_a$ 和 $p_b$，将 $p_a$ 和 $p_b$ 从 $\{p_i\}$ 中删除掉，然后将它们的和加入到 $\{p_i\}$ 中。这个过程的费用记为 $p_a + p_b$。
2. 重复步骤 1，直到 $\{p_i\}$ 中只剩下一个数。

在上面的操作过程中，把所有的费用相加，就得到了构造 Huffman 树的总费用。

本题任务：对于给定的一个数列，现在请你求出用该数列构造 Huffman 树的总费用。

例如，对于数列 $\{p_i\} = \{5, 3, 8, 2, 9\}$，Huffman 树的构造过程如下：

1. 找到 $\{5, 3, 8, 2, 9\}$ 中最小的两个数，分别是 2 和 3，从 $\{p_i\}$ 中删除它们并将和 5 加入，得到 $\{5, 8, 9, 5\}$，费用为 5。
2. 找到 $\{5, 8, 9, 5\}$ 中最小的两个数，分别是 5 和 5，从 $\{p_i\}$ 中删除它们并将和 10 加入，得到 $\{8, 9, 10\}$，费用为 10。
3. 找到 $\{8, 9, 10\}$ 中最小的两个数，分别是 8 和 9，从 $\{p_i\}$ 中删除它们并将和 17 加入，得到 $\{10, 17\}$，费用为 17。
4. 找到 $\{10, 17\}$ 中最小的两个数，分别是 10 和 17，从 $\{p_i\}$ 中删除它们并将和 27 加入，得到 $\{27\}$，费用为 27。
5. 现在，数列中只剩下一个数 27，构造过程结束，总费用为 $5 + 10 + 17 + 27 = 59$。

输入格式

输入的第一行包含一个正整数 $n$（$n \leq 100$）。

接下来是 $n$ 个正整数，表示 $p_0, p_1, \dots, p_{n-1}$，每个数不超过 1000。

输出格式

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

样例输入

5
5 3 8 2 9

样例输出

59