题目描述

给定 n（2≤n≤100）个正整数权值 wi，求构造哈夫曼树后的最小带权路径长度WPL。

输入格式

2行，第1行一个整数n（2≤n≤100）。第2行，n个空格隔开的正整数权值。

输出格式

输出WPL。

样例

输入样例 1

3
1 2 9

输出样例 1

15

输入样例 2

10
3 5 1 7 6 4 2 5 4 1

输出样例 2

120

输入样例 3

9
6 2 8 0 4 7 9 3 5

输出样例 3

130