問題文

$N$ 匹のスライムと $M$ 個の箱があります。スライム $i(1\le i\le N)$ の価値は $V_i$ です。スライムおよび箱には番号が振られており、それぞれスライム $i(1\le i\le N)$、 箱 $j(1\le j\le M)$ と表記します。

これから $N$ 匹の各スライムを $M$ 個の箱のいずれか $1$ つに入れます ($1$ 匹もスライムが入っていない箱が存在してもかまいません)。 スライムと箱の間には相性があり、これは長さ $M$ で o, x のみからなる文字列 $S_i$ で表されます。 $S_i$ の $j$ 文字目が o のとき、スライム $i$ を箱 $j$ に入れることができますが、x のときは入れることができません。

${\displaystyle \sum _{j=1}^M(}$箱 $j$ に入っているスライムの価値の総和${)}^2$ が最大でいくつになるか求めてください。

入力

$N$ $M$
$V_1$ $V_2$ $\dots$ $V_N$
$S_1$
$S_2$
$⋮$
$S_N$

• $1\le N\le {10}^5$
• $1\le M\le 20$
• $1\le V_i\le {10}^4$
• $|S_i|=M$
• $S_i$ は o を $1$ 文字以上含む
• 与えられる入力は（$S_i$ 以外）すべて整数

出力

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

最後に改行してください。

サンプル

3 3
3 4 5
ooo
oox
xox

144

4 2
2 3 6 5
ox
xo
oo
xo

200

13 6
404 386 221 993 1 708 468 832 20 879 704 589 311
xoxxxx
xooxox
oxxoxx
xoooox
ooxoox
oxooxo
xxxxoo
xooxox
ooooox
xxooxo
xxooxx
xxoxox
oxxxoo

26942778