题目描述

在“字符串评鉴大会”上，由小写字母构成的非空字符串 $S$ 的由 $N$ 条标准决定：

每条标准是一个字符串 $T_i$ （$T_i$ 的长度不超过 $3$）和对应的得分 $P_i$，$S$ 的“美丽度”定义为：

其中 $C_i$ 为 $T_i$ 在 $S$ 中出现的次数。

字符串 $V$ 在字符串 $U=U_1U_2 \cdots U_{|U|}$ 中出现的次数定义为：满足 $1\le i\le \vert U\vert -\vert V\vert +1$ 且 $U_iU_{i+1}\cdots U_{i+\vert V\vert -1}=V$ 的整数 $i$ 的数量，其中 $\vert U\vert$ 表示字符串 $U$ 的长度。

现在给出 $N$ 条标准，求出这 $N$ 条标准下“美丽度”最大的非空字符串 $S$ 的“美丽度”。如果这个答案是无限大，输出 Infinity。

输入格式

第一行输入一个整数 $N$

接下来 $N$ 行每行一个字符串 $T$ 和一个整数 $P$

输出格式

输出一个整数代表答案。若可以无限大，输出 Infinity

3
a -5
ab 10
ba -20

Infinity

28
a -5
ab 10
ba -20
bb -20
bc -20
bd -20
be -20
bf -20
bg -20
bh -20
bi -20
bj -20
bk -20
bl -20
bm -20
bn -20
bo -20
bp -20
bq -20
br -20
bs -20
bt -20
bu -20
bv -20
bw -20
bx -20
by -20
bz -20

5

26
a -1
b -1
c -1
d -1
e -1
f -1
g -1
h -1
i -1
j -1
k -1
l -1
m -1
n -1
o -1
p -1
q -1
r -1
s -1
t -1
u -1
v -1
w -1
x -1
y -1
z -1

-1

样例解释

样例 $1$：$S$ 为 $X$ 个 $\texttt{abz}$ 相连时，它的“美丽度”是 $5X$，所以 $S$ 的最大“美丽度”无限大。

样例 $2$：$S=\texttt{ab}$ 时“美丽度”最大。

样例 $3$：请注意 $S$ 不能为空。

数据范围

• $1\le N\le 18278$，$N$ 为整数。
• $1\le \vert T_i\vert \le 3$，$T_i$ 只包含小写字母。
• 若 $i\neq j$，则 $T_i\neq T_j$。
• $-10^9\le P_i\le 10^9$。
• $P_i$ 均为整数。