Huffman Code Length

Huffman coding gives each character of a text its own string of bits: short ones for common characters, longer ones for rare characters, and never one that is the start of another, so the bits can be read back without separators. Write huffman_bits(text) that returns the number of bits the Huffman-coded text takes (the coded text only, not the table of codes).

Build the code like this:

• start with one group for each distinct character, weighted by how many times that character appears in the text;
• take the two groups with the smallest weights and merge them into one group whose weight is the sum of theirs; every character inside the two merged groups gets one more bit in its code;
• repeat until one group is left.

A character's code length is the number of merges it took part in, and the answer is the sum of (number of times it appears) * (code length) over all characters. When several groups tie for the smallest weight, any choice leads to the same total, so the answer does not depend on how you break ties.

If the text has only one distinct character, each character takes 1 bit. The empty text takes 0 bits.

Examples

huffman_bits("aaabbc")       # returns 9
huffman_bits("abracadabra")  # returns 23
huffman_bits("zzzz")         # returns 4
huffman_bits("")             # returns 0

In "aaabbc", c (weight 1) and b (weight 2) merge first into a group of weight 3, which then merges with a (weight 3). So a gets a 1-bit code and b and c get 2-bit codes: 3 * 1 + 2 * 2 + 1 * 2 = 9 bits, instead of the 12 that 2 bits per character would need.

Constraints

• text has 0 to 200,000 characters, with up to 20,000 different characters.