11427: 【模板】哈夫曼编码
[Creator : ]
Description
给出一个有 $n$ 种字符组成的字符串，其中第 $i$ 种字符出现的次数为 $a_i$。
请你对该字符串应用哈夫曼编码，使得该字符串的长度尽可能短，求编码后的字符串的最短长度。
请你对该字符串应用哈夫曼编码，使得该字符串的长度尽可能短，求编码后的字符串的最短长度。
Input
第一行输入一个整数 $n\ (1≤n≤2⋅10^5)$，表示字符种数。
第二行输入 $n$ 个整数 $a_i\ (1≤a_i≤10^9)$，表示每种字符的出现次数。
第二行输入 $n$ 个整数 $a_i\ (1≤a_i≤10^9)$，表示每种字符的出现次数。
Output
输出一行一个整数，表示编码后字符串的最短长度。
Sample 1 Input
3
1 2 3
Sample 1 Output
9
三种字符的哈夫曼编码分别为
[00, 01, 1] 时，长度最短，最短长度为 $9$。 Sample 2 Input
5
1 2 2 5 9
Sample 2 Output
37
Sample 3 Input
3
5 11 30
Sample 3 Output
62
2
2 8
10