Problem J: 哈夫曼树

Problem J: 哈夫曼树

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MiB

Description

给定各叶子结点的权值,构造哈夫曼树,输出该哈夫曼树的带权路径长度

Input

第一行:整数 $n\ (1\leq n\leq 50)$
第二行:$n$ 个整数,为叶子结点的权值(权值 $w$ 满足:$1\leq w\leq 100$)

Output

一个整数,为这棵树的带权路径长度

Sample 1 Input

3
1 2 3

Sample 1 Output

9