We want to encode a given string SS to a binary string. Each alphabet character in SS should be mapped to a different variable-length code and the code must not be a prefix of others.
Huffman coding is known as one of ways to obtain a code table for such encoding.
For example, we consider that appearance frequencycies of each alphabet character in SS are as follows:
| a | b | c | d | e | f | |
|---|---|---|---|---|---|---|
| freq. | 45 | 13 | 12 | 16 | 9 | 5 |
| code | 0 | 101 | 100 | 111 | 1101 | 1100 |
We can obtain "Huffman codes" (the third row of the table) using Huffman's algorithm.
The algorithm finds a full binary tree called "Huffman tree" as shown in the following figure.
To obtain a Huffman tree, for each alphabet character, we first prepare a node which has no parents and a frequency (weight) of the alphabet character. Then, we repeat the following steps:
- Choose two nodes, xx and yy, which has no parents and the smallest weights.
- Create a new node zz whose weight is the sum of xx's and yy's.
- Add edge linking zz to xx with label 00 and to yy with label 11. Then zz become their parent.
- If there is only one node without a parent, which is the root, finish the algorithm. Otherwise, go to step 1.
Finally, we can find a "Huffman code" in a path from the root to leaves.
Task
Given a string SS, output the length of a binary string obtained by using Huffman coding for SS.