Марина недавно изучила алгоритм Хаффмана. Она помнит, что идея, положенная в основу кодировании Хаффмана, основана на частоте появления символа в последовательности. Символ, который встречается в последовательности чаще всего, получает очень маленький код, а символ, который встречается реже всего, получает, наоборот, очень длинный код. Марина решила поупражняться в кодировании на примере своей любимой скороговорки: флюорографист флюорографировал флюорографистку Определите, сколько бит будет содержать скороговорка после кодирования. Не забудьте, что пробелы также кодируются, как и все остальные символы (буквы). Слова разделены одинарными пробелами, перед первым словом и после последнего пробелов нет. В качестве ответа выведите одно целое число — количество бит в сжатой строке, например, 1.

Частота Буквы Код
7 о  11
7 р  101
6 ф 100
4 а  0111
4 л  0110
3 г   0101
3 и  0100
3 ю 00111
3 _  00110
2 с  00101
2 т  00100
1 в  00011
1 к  00010
1 у  00001
Итого: 7*2+7*3+6*3+4*4+4*4+3*4+3*4+3*5+3*5+2*5+1*5+1*5+1*5 = 164

Главное помнить, что структура кода префиксная, т.е код любого символа не должен совпадать с началом другого. Удачи!