도시

정사각형 나라는 $N \times N$개의 정사각형 구역으로 나누어진 격자 형태이다. 지도에는 개발된 구역이 $1$, 개발되지 않은 구역이 $0$으로 표시되어 있다. 어떤 구역이 개발되어 있고 상하좌우로 인접한 4개의 구역도 모두 개발되어 있으면, 이 구역은 도시가 된다. 가장자리에 있는 구역은 도시가 될 수 없다.

각 구역은 관광가치를 갖는다. $i$번째 행의 $j$번째 칸이 도시가 되면 이 구역의 관광가치는 $V_{ij}$이고, 도시가 아니면 관광가치는 $0$이다.

정사각형 나라에는 $K$개의 구역을 추가로 개발할 자본이 있다. 나라가 그다지 부유하지 않아서 $K$는 항상 개발되지 않은 구역의 수보다 작거나 같다. 관광 수익을 최대화하기 위해 $K$개의 구역을 새로 개발한 뒤, 도시의 관광가치 합의 최댓값을 구하라.

첫 번째 줄에 $N$, $K$가 공백으로 구분되어 주어진다.

두 번째 줄부터 $N$개의 줄에 걸쳐 $i$번째 줄에 지도 $M_{i1}, M_{i2}, \cdots, M_{iN}$이 공백으로 구분되어 주어진다. $M_{ij}$가 $1$이면 $i$번째 행의 $j$번째 칸은 이미 개발되어 있고, $0$이면 개발되어 있지 않다.

$N+2$번째 줄부터 $N$개의 줄에 걸쳐 $i$번째 줄에 각 구역의 관광가치 $V_{i1}, V_{i2}, \cdots, V_{iN}$이 공백으로 구분되어 주어진다.

$K$개의 구역을 개발한 후 도시의 관광가치 합의 최댓값을 출력한다.

• 주어지는 모든 수는 정수이다.
• $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$는 항상 개발되지 않은 구역의 수보다 작거나 같다.