题目描述

输入n（2<=n<=100）个非空字符和字符的出现频率（这些信息按频率的降序输入）。请给这些字符进行哈夫曼编码，然后输出编码最长的字符的编码长度（以比特为单位）。

输入格式

多行。第1行一个整数n。后面n行，每行是一个字符和字符的频率。

输出格式

编码最长的字符的编码长度（以比特为单位）。

样例

输入样例 1

4
C 6
A 5
D 3
B 1

输出样例 1

3

输入样例 2

4
C 6
A 5
B 3
D 3

输出样例 2

3

输入样例 3

18
n 4
a 3
e 3
f 3
i 3
h 2
m 2
o 2
s 2
c 1
d 1
g 1
l 1
p 1
r 1
t 1
u 1
x 1

输出样例 3

6