남욱이의 썩은 계란판

시간 제한4초메모리 제한512 MB

요약

N×N 계란판에 최대 K개의 도미노 덮개를 겹치지 않게 놓아 가린 썩음값 합을 최대화하고 남은 합을 구합니다.

난이도: 보통10점 중 7점
유형: 백트래킹, 정렬, 행렬
정답자: 아직 제출이 없습니다

문제

남욱이는 계란을 $N \times N$ 크기의 계란판에 담아서 판다. 계란마다 얼마나 썩었는지를 나타내는 썩음도가 붙어 있고, 값이 클수록 더 썩은 계란이다. 요즘 연애에 빠져 지내는 사이 계란을 방치해서 여러 개가 썩어버렸다. 남욱이는 가림판으로 썩은 계란을 가려 겉으로 보이는 썩음도의 합을 낮추려고 한다.

가림판은 다음 규칙을 따른다.

가림판 하나는 가로나 세로로 인접한 계란 두 개를 함께 가린다.
가림판끼리 겹칠 수 없다. 서로 닿는 것은 괜찮다.
가림판은 $K$ 개까지 놓을 수 있고, 전부 쓰지 않아도 된다.

가려지지 않은 계란의 썩음도 합이 가장 작아지도록 가림판을 놓았을 때, 그 합의 최솟값을 구하자.

입력

첫째 줄에 계란판의 크기 $N$ 과 가림판의 개수 $K$ 가 공백을 두고 주어진다. ( $1 \le N \le 2000$ , $1 \le K \le 8$ )

다음 $N$ 개의 줄에 각각 계란 $N$ 개의 썩음도 $F$ 가 공백을 두고 주어진다. ( $0 \le F \le 1000$ )

출력

가려지지 않은 계란의 썩음도 합의 최솟값을 첫째 줄에 출력한다.

예제2

예제 1
입력
```
3 1
2 7 6
9 5 1
4 3 8
```
예상 출력
```
31
```
예제 2
입력
```
4 2
1 2 4 0
4 0 5 4
0 3 5 1
1 0 4 1
```
예상 출력
```
17
```