問題文

文字列品評会では、英小文字のみからなる空でない文字列 $S$ に対して、その「美しさ」を決定します。

文字列 $S$ の美しさは、$N$ 個の審査項目の点数の和として定められます。 $i = 1, 2, \\ldots, N$ について、$i$ 番目の審査項目の点数は 「文字列 $T_i$（入力で与えられる長さ $3$ 以下の文字列）が $S$ に連続な部分文字列として含まれる回数」に $P_i$ を掛けて得られる値です。

英小文字のみからなる空でない文字列 $S$ の美しさとしてあり得る最大値を出力して下さい。 ただし、美しさとしていくらでも大きい値が考えられる場合は、代わりに Infinity と出力して下さい。

ここで、文字列 $U = U_1U_2\\ldots U_{|U|}$ に文字列 $V$ が連続な部分列として含まれる回数とは、 $1 \\leq i \\leq |U|-|V|+1$ を満たす整数 $i$ であって $U_iU_{i+1}\\ldots U_{i+|V|-1} = V$ を満たすものの個数です。

制約

• $1 \\leq N \\leq 18278$
• $N$ は整数
• $T_i$ は英小文字のみからなる長さ $1$ 以上 $3$ 以下の文字列
• $i \\neq j \\Rightarrow T_i \\neq T_j$
• $\-10^9 \\leq P_i \\leq 10^9$
• $P_i$ は整数

入力

入力は以下の形式で標準入力から与えられる。

$N$ $T_1$ $P_1$ $T_2$ $P_2$ $\\vdots$ $T_N$ $P_N$

出力

英小文字のみからなる空でない文字列 $S$ の美しさとしてあり得る最大値を出力せよ。 ただし、美しさとしていくらでも大きい値が考えられる場合は、代わりに Infinity と出力せよ。

入力例 1

3
a -5
ab 10
ba -20

出力例 1

Infinity

例えば、$S =$ abzabz について、

• $1$ 番目の審査項目の点数は、a が $S$ に連続な部分列として含まれる回数が $2$ 回であることから、$2 \\times (-5) = -10$ 点
• $2$ 番目の審査項目の点数は、ab が $S$ に連続な部分列として含まれる回数が $2$ 回であることから、$2 \\times 10 = 20$ 点
• $3$ 番目の審査項目の点数は、ba が $S$ に連続な部分列として含まれる回数が $0$ 回であることから、$0 \\times (-20) = 0$ 点

であるので、$S$ の美しさは $(-10) + 20 + 0 = 10$ となります。

別の例として、$S =$ abzabzabz について、

• $1$ 番目の審査項目の点数は、a が $S$ に連続な部分列として含まれる回数が $3$ 回であることから、$3 \\times (-5) = -15$ 点
• $2$ 番目の審査項目の点数は、ab が $S$ に連続な部分列として含まれる回数が $3$ 回であることから、$3 \\times 10 = 30$ 点
• $3$ 番目の審査項目の点数は、ba が $S$ に連続な部分列として含まれる回数が $0$ 回であることから、$0 \\times (-20) = 0$ 点

であるので、$S$ の美しさは $(-15) + 30 + 0 = 15$ となります。

一般に、正の整数 $X$ について、abz を $X$ 回繰り返した文字列の美しさは $5X$ となります。 $S$ の美しさとしていくらでも大きい値が考えられるため、Infinity を出力します。

入力例 2

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

出力例 2

5

$S =$ ab が考えられる美しさの最大値を達成します。

入力例 3

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

出力例 3

-1

$S$ は空でない文字列でなければならないことに注意して下さい。