実行時間制限: 2 sec / メモリ制限: 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.