問題文

$2N$ 行 $2N$ 列のマス目があり，どのマスも白か黒の色で塗られています．このマス目の $i$ 行 $j$ 列目のマスのことを，マス $(i,j)$ と表します．

最初，$S_{i,j}=$ # ならばマス $(i,j)$ が黒で塗られており，$S_{i,j}=$ .ならばマス $(i,j)$ が白で塗られています．

マス目に対して，次の状態が満たされているとき，マス目はシンメトリーであると言います．

• マス目を左右反転させたものと，もとのマス目に対して，全てのマスの色が等しい．
• 厳密には，$1 \leq i \leq 2N, 1 \leq j \leq 2N$ を満たすすべての $i,j$ に対して，マス$(i, j)$ とマス $(i, 2N + 1 - j)$ の色は等しい．

はちじくんは，このマス目に対して，次のような操作を $0$ 回以上の何回でも行うことができます．

• 白で塗られたマスと，黒で塗られたマスを，一つずつ選ぶ．白で塗られていた方のマスの色を黒に，黒で塗られていた方のマスの色を白に変える．

マス目がなるべく整っているべきだと思っているはちじくんは，マス目の綺麗さを最大化したいです．マス目の綺麗さは次のように計算されます．

• 黒で塗られているようなマス $(i,j)$ すべてに対して， $C_{i,j}$ を足し合わせた値が，マス目の綺麗さである．
• ただし，それに加えて，マス目がシンメトリーであるならば，マス目の綺麗さは $K$ 増加する．

達成可能な綺麗さの最大値を求めてください．

入力

$N$ $K$
$S_1$
$S_2$
$\vdots$
$S_{2N}$
$C_{1,1}$ $C_{1,2}$ $\cdots$ $C_{1,2N}$
$C_{2,1}$ $C_{2,2}$ $\cdots$ $C_{2,2N}$
$\vdots$
$C_{2N,1}$ $C_{2N,2}$ $\cdots$ $C_{2N,2N}$

• $N, K, C_{i,j}$ は整数である．
• $1 \leq N \leq 250$
• $0 \leq K \leq 10^{14}$
• $S_{i}$ は #，. からなる長さ $2N$ の文字列である．
• $-10^9 \leq C_{i,j} \leq 10^9$

出力

答えを出力せよ．

サンプル

1 22
#.
.#
13 41
39 8

80

1 39
#.
.#
13 41
39 8

93

1 1000000000
##
##
-1000000000 -1000000000
-1000000000 -1000000000

-3000000000