题目描述

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

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

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

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

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

输入格式

输入的第一行包含一个正整数 $n$（$n\le 100$）。 接下来是 $n$ 个正整数，表示 $p_0, p_1, \dots p_{n−1}$，每个数不超过 $1000$。

输出格式

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

5
5 3 8 2 9

59