32130번 - 도시 서브태스크

문제

정사각형 나라는 $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$는 항상 개발되지 않은 구역의 개수보다 작거나 같다.

서브태스크

힌트