AT_abc264_g [ABC264G] String Fair

题目描述

在字符串品评会上，对于仅由小写英文字母组成的非空字符串 $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$ 且 $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。

输入输出样例 #1

输入 #1

3
a -5
ab 10
ba -20

输出 #1

Infinity

输入输出样例 #2

输入 #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

输入输出样例 #3

输入 #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

说明/提示

限制条件

• $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$ 为整数

样例解释 1

例如，对于 $S = \text{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 = \text{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

$S = \text{ab}$ 可以取得最大美丽度。

样例解释 3

请注意，$S$ 必须是非空字符串。

由 ChatGPT 4.1 翻译