配点 : $600$ 点

問題文

文字列品評会では、英小文字のみからなる空でない文字列 $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 と出力せよ。

3
a -5
ab 10
ba -20

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 を出力します。

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

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

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

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