故事背景

在现代计算机系统中，数据压缩是一项重要的技术，它可以减少数据存储所需的空间和传输所需的时间。霍夫曼编码是一种经典的数据压缩算法，通过为出现频率高的字符分配较短的编码，为出现频率低的字符分配较长的编码，从而达到最优的压缩效果。作为一名数据压缩专家，你需要实现霍夫曼编码算法，计算给定字符频率下的最小总编码长度。

题目描述

给定一组字符及其出现频率，计算使用霍夫曼编码时的最小总编码长度。

霍夫曼编码的基本思想是：

1. 将所有字符看作一个节点，权重为其出现频率
2. 每次选择两个权重最小的节点，合并为一个新节点，权重为两个节点权重之和
3. 重复步骤2，直到只剩下一个节点（根节点）
4. 从根节点到每个叶子节点的路径即为该字符的编码，左子树为0，右子树为1

总编码长度是指每个字符的编码长度乘以其出现频率的总和。

输入格式

第一行输入一个整数 n （ $1 \leq n \leq 1000$ ），表示字符的种类数。

接下来 n 行，每行输入一个字符和一个整数 f （ $1 \leq f \leq 1000$ ），分别表示字符和其出现频率。

输出格式

输出一个整数，表示使用霍夫曼编码时的最小总编码长度。

样例输入 1

4
a 5
b 9
c 12
d 13

样例输出 1

60

样例输入 2

6
A 45
B 13
C 12
D 16
E 9
F 5

样例输出 2

224

样例输入 3

2
X 1
Y 2

样例输出 3

3

提示

• 这是一个经典的霍夫曼编码问题，贪心算法可以得到最优解
• 可以使用优先队列（最小堆）来高效地选择两个权重最小的节点
• 注意处理只有一个字符的情况
• 总编码长度的计算方法：每个字符的编码长度乘以其频率的总和