ハフマン符号

与えられた文字列に出現する各文字の種類ごとに異なるビット文字列の符号語を割り当てて文字列をビット文字列へ符号化したいです。この時、どの符号語も別の符号語の接頭語とならないように符号語を割り当てると、得られたビット文字列符号から一意に元の文字列を定めることができます。

このような符号語の割り当てを求める方法の一つに、ハフマンの符号化アルゴリズムがあります。さらに、このアルゴリズムは任意の文字列について最短の自然数長ビット文字列符号をもたらすことが知られています。

例として、各文字ごとの出現頻度が以下の表のような文字列について考えます。ハフマンの符号化アルゴリズムを用いると表の3段目のような符号語を得ることができ、これが最適な符号語の割り当てとなります。

	a	b	c	d	e	f
出現頻度	45	13	12	16	9	5
符号語	0	101	100	111	1101	1100

ハフマンの符号化アルゴリズムは、以下の図のようなハフマン木と呼ばれる全二分木を構成します。

ハフマン木を構成するためには、まずそれぞれの文字の種類ごとに、文字の種類とその出現頻度を持つ親を持たない頂点を作ります。その後、手順を繰り返します。

ハフマン木の葉を除く各頂点の左の子への辺と右の子への辺のそれぞれに0と1を割り当てることで、根から各文字の葉へ向かうパス上に対応する符号を見て取ることができます。

課題

文字列 $S$ が入力として与えられるので、ハフマンの符号化アルゴリズムを用いて $S$ の各文字に符号語を割り当てたときに、$S$ を符号化して得られるビット文字列の長さを出力するプログラムを作成してください。

$S$

文字列 $S$ が1行に与えられます。

ビット文字列の長さを1行に出力してください。

abca

例えば上記のアルゴリズムを利用して、aに0、bに10、cに11を符号語として割り当てると、得られるビット列は010110となり、6が答えになります。

aaabbcccdeeeffg