City

A square country is a grid of $N \times N$ square regions. A map marks each region as $1$ if it is developed and $0$ if it is not. A region is a city if it is developed and all four regions adjacent to it (up, down, left, and right) are also developed. A region on the edge cannot be a city.

Each region has a tourism value. If the cell in row $i$, column $j$ becomes a city, its tourism value is $V_{ij}$. Otherwise, its tourism value is $0$.

The country has capital to develop $K$ more regions. The country is not wealthy, so $K$ is always less than or equal to the number of undeveloped regions. To maximize tourism revenue, find the maximum possible sum of tourism values of the cities after developing $K$ new regions.

The first line contains $N$ and $K$, separated by a space.

From the second line onward, the next $N$ lines describe the map. Line $i$ contains $M_{i1}, M_{i2}, \cdots, M_{iN}$, separated by spaces. If $M_{ij}$ is $1$, the cell in row $i$, column $j$ is already developed. If $M_{ij}$ is $0$, it is not.

From line $N+2$ onward, the next $N$ lines contain the tourism values. Line $i$ contains $V_{i1}, V_{i2}, \cdots, V_{iN}$, separated by spaces.

Print the maximum sum of tourism values of the cities after developing $K$ regions.

• All given numbers are integers.
• $3 \leq N \leq 12$
• $0 \leq K \leq 50$
• $M_{ij} \in \{0, 1\}$ ($1 \le i,j \le N$)
• $0 \leq V_{ij} \leq 1\,000\,000$ ($1 \le i,j \le N$)
• $K$ is always less than or equal to the number of undeveloped regions.