该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述：

哈夫曼树的定义是：一棵具有 n 个带权叶结点的二叉树，使得所有叶结点的带权路径长度（叶结点 × 叶结点到根结点的路径长度）之和最小，这样的二叉树被称为最优二叉树，也称哈夫曼树。

请读入一个整数 n ，代表叶结点的数量，再读入 n 个整数，代表叶结点的权值，请求出对应哈夫曼树的带权路径长度。

输入格式：

输入的第一行包含一个正整数 n。

接下来是 n 个正整数，表示 n 个叶结点的权值，每个数不超过 1000。

输出格式：

输出构造出的哈夫曼树的带权路径长度。

样例：

5
5 3 8 2 9

59

提示

n≤100