当前没有测试数据。

题目描述

哈夫曼编码是一种用于无损数据压缩的编码方法。它根据每个字符在文本中出现的频率，为每个字符分配一个变长的二进制编码，使得出现频率高的字符拥有较短的编码，出现频率低的字符拥有较长的编码，从而使得整个文本的编码总长度最小。

构造哈夫曼编码的过程可以借助一棵二叉树（哈夫曼树）来完成：

1. 统计文本中每个字符的出现次数（即频率）。

2. 将每个字符看作一个叶子节点，节点的权值为该字符的频率。

3. 每次选择两个权值最小的节点，将它们合并成一个新节点，新节点的权值为这两个节点的权值之和。这个新节点将成为这两个节点的父节点。

4. 重复上述步骤，直到只剩下一个节点（即哈夫曼树的根节点）。

5. 从根节点出发，给每个左分支标上 0，右分支标上 1（或相反），则从根到每个叶子节点的路径上的 0/1 序列就是该叶子节点对应字符的哈夫曼编码。

输入格式

仅一行，一个仅包含 ASCII 可见字符的字符串 $s (0 \leq |s| \leq 10^6)$

其中 $|s|$ 的意思为字符串 $s$ 的长度

输出格式

仅一行，一个整数，表示哈夫曼编码后该字符串所占的位数

输入输出样例

SATSAACTATCSATAASAT

36

样例解释

对于字符串"SATSAACTATCSATAASAT"

方框中的数表示对应字母的出现顺序，我们将出现次数最小的C和S先放在一起，他们的总出现次数为六，再将当前最小的T和(CS)放在一起，以此类推。然后，将数的左边记为0，右边记为1，就得到了每个字母的编码。可以证明，这样的编码无论怎么排列，都不会有歧义。

最终我们得到的编码为

111 0 10 111 0 0 110 10 0 10 110 111 0 10 0 0 111 0 10

总长度为 $36$