AT_abc264_g [ABC264G] String Fair

[problemUrl]: https://atcoder.jp/contests/abc264/tasks/abc264_g 文字列品評会では、英小文字のみからなる空でない文字列 $ 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 $ を満たすものの個数です。

N/A

N/A

### 制約 - $ 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 $ は整数 ### Sample Explanation 1 例えば、$ 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` を出力します。 ### Sample Explanation 2 $ S\ = $ `ab` が考えられる美しさの最大値を達成します。 ### Sample Explanation 3 $ S $ は空でない文字列でなければならないことに注意して下さい。