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

题目描述

给定 ( N ) 个权值作为 ( N ) 个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。

现在，给定 ( N ) 个叶子结点的信息，请你构造哈夫曼树，并输出该树的带权路径长度。

输入格式

第一行包含整数 ( N )，表示叶子结点数量。

第二行包含 ( N ) 个整数，表示每个叶子结点的权值。

输出格式

输出一个整数，表示生成哈夫曼树的带权路径长度。

样例

样例输入

5
1 2 2 5 9

样例输出

37

数据范围与提示

• $( 2 \leq N \leq 1000 )$
• 叶子结点的权值范围 ([1, 100])