字符串展览会

题目描述

在一个字符串展览会上,由小写英文字母组成的非空字符串 $S$ 的美观度按如下方式确定。

字符串 $S$ 的美观度等于由 $N$ 个评价标准决定的 $N$ 个分数的总和。

对于第 $i$ 个标准($i = 1, 2, \ldots, N$),其决定的分数是「输入中给出的长度至多为 $3$ 的字符串 $T_i$ 在 $S$ 中作为连续子序列出现的次数」乘以 $P_i$。

输出由小写英文字母组成的非空字符串 $S$ 的美观度可能达到的最大值。

如果可以获得无限大的美观度,则输出 Infinity。

这里,字符串 $V$ 在字符串 $U = U_1U_2\ldots U_{|U|}$ 中作为连续子序列出现的次数,定义为满足 $1 \le i \le |U|-|V|+1$ 且 $U_iU_{i+1}\ldots U_{i+|V|-1} = V$ 的整数 $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$ 个标准决定的分数是 $2 \times (-5) = -10$ 分,因为 a 在 $S$ 中作为连续子序列出现了 $2$ 次。

第 $2$ 个标准决定的分数是 $2 \times 10 = 20$ 分,因为 ab 在 $S$ 中作为连续子序列出现了 $2$ 次。

第 $3$ 个标准决定的分数是 $0 \times (-20) = 0$ 分,因为 ba 在 $S$ 中作为连续子序列出现了 $0$ 次。

因此,$S$ 的美观度为 $(-10) + 20 + 0 = 10$。

再如,若 $S =$ abzabzabz:

第 $1$ 个标准决定的分数是 $3 \times (-5) = -15$ 分,因为 a 在 $S$ 中作为连续子序列出现了 $3$ 次。

第 $2$ 个标准决定的分数是 $3 \times 10 = 30$ 分,因为 ab 在 $S$ 中作为连续子序列出现了 $3$ 次。

第 $3$ 个标准决定的分数是 $0 \times (-20) = 0$ 分,因为 ba 在 $S$ 中作为连续子序列出现了 $0$ 次。

因此,$S$ 的美观度为 $(-15) + 30 + 0 = 15$。

一般地,对于正整数 $X$,若 $S$ 是 $X$ 份 abz 的连接,则 $S$ 的美观度为 $5X$。

由于可以获得任意大的美观度,因此应输出 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$ 必须是非空字符串。

数据范围

• $1 \le N \le 18278$
• $N$ 为整数。
• $T_i$ 是由小写英文字母组成的长度在 $1$ 到 $3$ 之间的字符串。
• $i \neq j \Rightarrow T_i \neq T_j$
• $-10^9 \le P_i \le 10^9$
• $P_i$ 为整数。