Keyboard Typing

注意

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

問題文

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

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

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

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

制約

• $1 \leqq N \leqq 10$
• $1 \leqq C_{i,x} \leqq 10^{13}$
• $1 \leqq Q \leqq 10^5$
• $W_i$ は英小文字からなる長さ $1$ 以上 $10^5$ 以下の文字列
• $W_1,W_2,...,W_Q$ の長さの総和は $10^5$ 以下

入力

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

出力

コストの最小値を $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

53

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

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

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

入出力例２

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

14

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

入出力例３

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

1234

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