Problem Statement

There is a grid with $2N$ rows and $2N$ columns, where each cell is painted either white or black. The cell in row $i$ and column $j$ of this grid is denoted by cell $(i,j)$.

Initially, cell $(i,j)$ is painted black if $S_{i,j}=$ #, and cell $(i,j)$ is painted white if $S_{i,j}=$ ..

The grid is said to be symmetric if the following condition is satisfied.

• The grid flipped horizontally and the original grid have the same color in every cell.
• Formally, for all $i,j$ satisfying $1 \leq i \leq 2N, 1 \leq j \leq 2N$, cell $(i, j)$ and cell $(i, 2N + 1 - j)$ have the same color.

Hachiji-kun can perform the following operation on this grid any number of times, possibly $0$ times.

• Choose one cell painted white and one cell painted black. Change the color of the cell that was white to black, and the color of the cell that was black to white.

Hachiji-kun, who thinks that the grid should be as neat as possible, wants to maximize the beauty of the grid. The beauty of the grid is calculated as follows.

• The beauty of the grid is the sum of $C_{i,j}$ over all cells $(i,j)$ painted black.
• In addition, if the grid is symmetric, the beauty of the grid increases by $K$.

Find the maximum achievable beauty.

Input

$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}$ are integers.
• $1 \leq N \leq 250$
• $0 \leq K \leq 10^{14}$
• $S_{i}$ is a string of length $2N$ consisting of # and ..
• $-10^9 \leq C_{i,j} \leq 10^9$

Output

Output the answer.

Sample

1 22
#.
.#
13 41
39 8

80

1 39
#.
.#
13 41
39 8

93

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

-3000000000