String Fair

题目描述

在一个字符串集市上，他们对由小写英文字母组成的非空字符串 $S$ 的美丽度进行判定。 字符串 $S$ 的美丽度等于由 $N$ 条标准决定的 $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$ 且 $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

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 \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$ 是整数。例如，如果 $S =$ $abzabz$：

由第 $1$ 条标准决定的分数是 $2 \times (-5) = -10$ 分，因为 $a$ 在 $S$ 中作为连续子序列出现了两次。 由第 $2$ 条标准决定的分数是 $2 \times 10 = 20$ 分，因为 $ab$ 在 $S$ 中作为连续子序列出现了两次。 由第 $3$ 条标准决定的分数是 $0 \times (-20) = 0$ 分，因为 $ba$ 在 $S$ 中作为连续子序列出现了 $0$ 次。

因此，$S$ 的美丽度为 $(-10) + 20 + 0 = 10$。 另一个例子，如果 $S =$ $abzabzabz$：

由第 $1$ 条标准决定的分数是 $3 \times (-5) = -15$ 分，因为 $a$ 在 $S$ 中作为连续子序列出现了三次。 由第 $2$ 条标准决定的分数是 $3 \times 10 = 30$ 分，因为 $ab$ 在 $S$ 中作为连续子序列出现了三次。 由第 $3$ 条标准决定的分数是 $0 \times (-20) = 0$ 分，因为 $ba$ 在 $S$ 中作为连续子序列出现了 $0$ 次。

因此，$S$ 的美丽度为 $(-15) + 30 + 0 = 15$。 一般地，对于正整数 $X$，如果 $S$ 是 $X$ 个 $abz$ 的连接，那么 $S$ 的美丽度为 $5X$。 由于你可以获得任意大的美丽度，应当输出 $Infinity$。
$S =$ $ab$ 达到可能的最大美丽度。
注意 $S$ 应当是一个非空字符串。

标签: AtCoder|abc264G

来源

AtCoder|abc264G