F - Waseda Orientation Contest 2021's Secret Last Problem

2 secs 1024 MB
bayashiko's icon bayashiko

F - Waseda Orientation Contest 2021's Secret Last Problem

配点 : 600600
  

問題文

bayashikoくんは紬さんに英小文字からなる長さ NN の文字列 SS を贈ろうと考えています。
bayashikoくんの語彙には MM 個の単語 W1,W2,,WMW_1,W_2,\ldots ,W_M があり、 ii 個目の単語の美しさは AiA_i です。
また、文字列 SS の価値を以下のように定義します。

  • SS の全ての連続部分文字列のうち WiW_i と等しいものの個数を CiC_i として、 i=1M(Ai×Ci)\displaystyle \sum_{i=1}^{M} (A_i×C_i)

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

  

制約

  • 1N10001\leq N \leq 1000
  • 1M501\leq M \leq 50
  • 1Ai1091\leq A_i \leq 10^9
  • 1Wi151\leq |W_i| \leq 15
  • Wi|W_i| の総和は 7575 を超えない
  • N,M,AiN,M,A_i は整数
  • WiW_i は英小文字からなる
  • iji \neq j ならば WiWjW_i \neq W_j

  

入力

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

N MN\ M
A1 A2  AMA_1 \ A_2 \ \ldots \ A_M
W1W_1
W2W_2
::
WMW_M

  

出力

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

  

入力例1

4 2
4 3
a
aaa

出力例1

22

文字列 SS として最適なのは aaaa です。
aaaa の連続部分文字列として a44 回、 aaa22 回現れるので、 aaaa の価値は 4×4+3×2=224×4+3×2=22 です。
このケースにおいてこれより価値の高い長さ 44 の文字列は存在しないので、答えは 2222 となります。  
 

入力例2

9 3
7 6 6
abc
cde
efa

出力例2

26

S=S= 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

Submit


Go (1.21)