#abc264g. [abc264_g]String Fair
[abc264_g]String Fair
Problem Statement
In a string fair, they determine the beauty of a non-empty string consisting of lowercase English letters.
The beauty of string equals the sum of scores determined by criteria. For , the score determined by the -th criterion is "the number of occurrences of a string (of length at most given in the Input) in as a consecutive subsequence" multiplied by .
Print the maximum possible beauty of a non-empty string 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 in a string as a consecutive subsequence is defined to be the number of integers such that and .
Constraints
- is an integer.
- is a string of length between and consisting of lowercase English letters.
- is an integer.
Input
Input is given from Standard Input in the following format:
Output
Print the maximum possible beauty of a non-empty string consisting of lowercase English letters. If it is possible to obtain infinitely large beauty, print Infinity
instead.
Sample Input 1
Sample Output 1
For example, if abzabz
:
- The score determined by the -st criterion is points, because
a
occurs twice in as a consecutive subsequence. - The score determined by the -nd criterion is points, because
ab
occurs twice in as a consecutive subsequence. - The score determined by the -rd criterion is points, because
ba
occurs times in as a consecutive subsequence.
Thus, the beauty of is .
As another example, if abzabzabz
:
- The score determined by the -st criterion is points, because
a
occurs times in as a consecutive subsequence. - The score determined by the -nd criterion is points, because
ab
occurs times in as a consecutive subsequence. - The score determined by the -rd criterion is points, because
ba
occurs times in as a consecutive subsequence.
Thus, the beauty of is .
In general, for a positive integer , if is a concatenation of copies of abz
, then the beauty of is . Since you can obtain as large beauty as you want, Infinity
should be printed.
Sample Input 2
Sample Output 2
ab
achieves the maximum beauty possible.
Sample Input 3
Sample Output 3
Note that should be a non-empty string.