F - Waseda Orientation Contest 2021's Secret Last Problem

2 secs 1024 MB
bayashiko

F - Waseda Orientation Contest 2021's Secret Last Problem


配点 :
  

問題文


bayashikoくんは紬さんに英小文字からなる長さ の文字列 を贈ろうと考えています。
bayashikoくんの語彙には 個の単語 があり、 個目の単語の美しさは です。
また、文字列 の価値を以下のように定義します。

  • の全ての連続部分文字列のうち と等しいものの個数を として、

bayashikoくんは紬さんになるべく価値の高い文字列を贈りたいと思っています。
文字列 として考えられるものは全部で 通りありますが、それらのうち最も価値の高いものの価値を求めてください。

  

制約


  • の総和は を超えない
  • は整数
  • は英小文字からなる
  • ならば

  

入力


入力は以下の形式で標準入力から与えられます。






  

出力


答えを出力してください。

  

入力例1


4 2
4 3
a
aaa

出力例1


22

文字列 として最適なのは aaaa です。
aaaa の連続部分文字列として a 回、 aaa 回現れるので、 aaaa の価値は です。
このケースにおいてこれより価値の高い長さ の文字列は存在しないので、答えは となります。  
 

入力例2


9 3
7 6 6
abc
cde
efa

出力例2


26

abcdefabc とするのが最適です。  
 

入力例3


133 3
6120 7011 3991
ushita
punichi
akun

出力例3


148565

 

入力例4


1000 4
20090306 19960227 19880420 19870403
goldship
haruurara
tokaiteio
mejiromcqueen

出力例4


2511288250

提出


Go (1.14)