注意

Pythonでの提出はPyPyを利用する事を推奨いたします。

問題文

NN 個のキーボードがあります。
各キーボードのキーは、英小文字 2626 キーから構成されており、全てのキーが1つずつ存在します。
ii 番目のキーボードを用いて文字 xx を入力するコストは Ci,x(1iN)C_{i,x}(1≤i≤N) となります。

あなたはこれから NN 個のキーボードを使い、QQ 個のワード Wi(1iQ)W_i(1≤i≤Q) を順に入力します。
ワード毎に、異なるキーボードを使う事が可能ですが、キーボードを変更した直後のワードでは、慣れていないためコストが 22 倍になります。

ただし、最初のワードについては、キーボードを変更していないので 22 倍のコストは発生しません。

全てのワードを入力し終えるのに必要なコストの最小値を求めてください。

制約

  • 1N101 \leqq N \leqq 10
  • 1Ci,x10131 \leqq C_{i,x} \leqq 10^{13}
  • 1Q1051 \leqq Q \leqq 10^5
  • WiW_i は英小文字からなる長さ 11 以上 10510^5 以下の文字列
  • W1,W2,...,WQW_1,W_2,...,W_Q の長さの総和は 10510^5 以下

入力

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

NN QQ
C1,a  C1,b  C1,z  C_{1,a}\; C_{1,b}\; \ldots C_{1,z}\;
C2,a  C2,b  C2,z  C_{2,a}\; C_{2,b}\; \ldots C_{2,z}\;
\vdots
CN,a  CN,b  CN,z  C_{N,a}\; C_{N,b}\; \ldots C_{N,z}\;
W1  W_1\;
W2  W_2\;
\vdots
WQ  W_Q\;

出力

コストの最小値を 11 行に出力してください。
 

入出力例1

入力例1
4 4
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
abc
xyz
ac
tle
出力例1
53

例えば以下のようにキーボードを使用する事で、コスト 5353 で全てのワードを入力出来ます。

  • キーボード 22 を使用する。1+2+3=61+2+3=6のコストが掛かる。
  • キーボード 33 に変更する。2×(3+2+1)=122×(3+2+1)=12 のコストが掛かる。
  • キーボード 11 に変更する。2×(5+5)=202×(5+5)=20 のコストが掛かる。
  • キーボード 11 をそのまま使用する。5+5+5=155+5+5=15 のコストが掛かる。

コストを53未満にする事は出来ません。
また、完全に同じキーボードが存在する場合がある事に注意してください。

入出力例2

入力例2
1 1
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
contest
出力例2
14

キーボードは一つしかない事もあります。

入出力例3

入力例3
5 7
2 3 7 12 7 5 113 25 105 62 29 211 3 37 4 1 1 2 10 5 2 1 6 169 1 50
103 63 5 7 28 3 2 9 15 190 107 2 1 30 142 6 43 2 6 10 1 17 194 239 2 1
7 2 4 8 16 3435 64 8 256 729 5 2048 3 9 8 32768 65536 7 1 5 2 5 3 2 6 8
10000000000000 49 1 8 1 5 124 12 1 9 7 3 1 3 1 9 1 4 1 57 3 11 5 8 2 15
2 22 1 2 1 5 8 2 2 5 1 1 2 4 8 4 5 8 4 3 5 3 4 4 3 333333333333
rawvdkcdp
chjlaxkpkhoqlpz
lbdjf
usachqelxisatiyyk
ivtdkaqk
efnwgddjvhxcns
ixobimz
出力例3
1234

コストは 3232 bit整数に収まらない場合があることに注意してください。
 

提出


Go (1.21)