题目描述
In computer science and information theory, a Huffman code is an optimal prefix code algorithm.
In this exercise, please use Huffman coding to encode a given data.
You should output the number of bits, denoted as B(T), to encode the data:
B(T)=∑f(c)dT(c),
where f(c) is the frequency of character c, and dT(c) is be the depth of character c's leaf in the tree T.
输入描述
The first line is the number of characters n.
The following n lines, each line gives the character c and its frequency f(c).
输出描述
Output a single number B(T).
输入样例
5
0 5
1 4
2 6
3 2
4 3输出样例
45