도시

정사각형 나라는 $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}$이 공백으로 구분되어 주어진다. $i$번째 행의 $j$번째 칸이 이미 개발되어 있우면 $M\_{ij} = 1$, 개발되어 있지 않으면 $M\_{ij} = 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$는 항상 개발되지 않은 구역의 개수보다 작거나 같다.