G - String Fair Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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 と出力せよ。

入力例 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 は空でない文字列でなければならないことに注意して下さい。

Score : 600 points

Problem Statement

In a string fair, they determine the beauty of a non-empty string S consisting of lowercase English letters.

The beauty of string S equals the sum of N scores determined by N criteria. For i = 1, 2, \ldots, N, the score determined by the i-th criterion is "the number of occurrences of a string T_i (of length at most 3 given in the Input) in S as a consecutive subsequence" multiplied by P_i.

Print the maximum possible beauty of a non-empty string S consisting of lowercase English letters. If it is possible to obtain infinitely large beauty, print Infinity instead.

Here, the number of occurrences of a string V in a string U = U_1U_2\ldots U_{|U|} as a consecutive subsequence is defined to be the number of integers i such that 1 \leq i \leq |U|-|V|+1 and U_iU_{i+1}\ldots U_{i+|V|-1} = V.

Constraints

  • 1 \leq N \leq 18278
  • N is an integer.
  • T_i is a string of length between 1 and 3 consisting of lowercase English letters.
  • i \neq j \Rightarrow T_i \neq T_j
  • -10^9 \leq P_i \leq 10^9
  • P_i is an integer.

Input

Input is given from Standard Input in the following format:

N
T_1 P_1
T_2 P_2
\vdots
T_N P_N

Output

Print the maximum possible beauty of a non-empty string S consisting of lowercase English letters. If it is possible to obtain infinitely large beauty, print Infinity instead.

Sample Input 1

3
a -5
ab 10
ba -20

Sample Output 1

Infinity

For example, if S = abzabz:

  • The score determined by the 1-st criterion is 2 \times (-5) = -10 points, because a occurs twice in S as a consecutive subsequence.
  • The score determined by the 2-nd criterion is 2 \times 10 = 20 points, because ab occurs twice in S as a consecutive subsequence.
  • The score determined by the 3-rd criterion is 0 \times (-20) = 0 points, because ba occurs 0 times in S as a consecutive subsequence.

Thus, the beauty of S is (-10) + 20 + 0 = 10.

As another example, if S = abzabzabz:

  • The score determined by the 1-st criterion is 3 \times (-5) = -15 points, because a occurs 3 times in S as a consecutive subsequence.
  • The score determined by the 2-nd criterion is 3 \times 10 = 30 points, because ab occurs 3 times in S as a consecutive subsequence.
  • The score determined by the 3-rd criterion is 0 \times (-20) = 0 points, because ba occurs 0 times in S as a consecutive subsequence.

Thus, the beauty of S is (-15) + 30 + 0 = 15.

In general, for a positive integer X, if S is a concatenation of X copies of abz, then the beauty of S is 5X. Since you can obtain as large beauty as you want, Infinity should be printed.

Sample Input 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

Sample Output 2

5

S = ab achieves the maximum beauty possible.

Sample Input 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

Sample Output 3

-1

Note that S should be a non-empty string.