문제
다이아몬드 광산을 운영하는 반딧불은 지난 jungol 왕국과의 거래로 많은 수익을 얻었다.
또한 지난 계약을 잘 이해한 덕분에 N * N 넓이에 대한 새로운 채굴 허가를 얻었다.
나름 좋은 조건에 채굴계약을 채결하였는데 계약서에 따르면 다음 세 가지를 꼭 준수해야 했다.
광산을 정방형의 그리드 모양으로 나누었을 때,
1. 각 행마다 연속한 K구간을 채굴한다. 2. 채굴한 곳들을 통로로 볼 때 채굴영역의 왼쪽 바깥과 오른쪽 바깥 사이에 경로가 생기지 않도록 해야 한다. 3. 채굴한 곳들을 통로로 볼 때 채굴영역의 위쪽 바깥과 아래쪽 바깥 사이에 경로가 생기지 않도록 해야 한다.
N=5이고 K=2인 경우를 예로 들어 살펴보자면 아래 그림들 중에 입력 예를 설명하고 있는 그림1만 가능한 경우가 된다.
그림2는 조건1를 어겼으며 그림3은 조건2를 어긴 경우이다. 그림4는 조건3을 어긴 경우이다.
사업가답게 반딧불은 N * N구간을 단위크기로 나누어 각 격자 크기의 영역에 대한 상품성을 조사한 가격표를 만들었다. 이제 채굴을 하려고 한다. 반딧불은 최대 얼마의 수익을 얻을 수 있을까?
입력
첫 행에 채굴 영역의 크기 N과 연속한 구간 크기 K가 공백으로 구분되어 입력된다. (2 <= N <= 250, 1<= K <= N/2)
다음 행부터 N개의 행에 걸쳐 채굴 영역의 정보가 공백으로 구분되어 입력된다. 입력되는 각 격자의 숫자는 1이상 1000미만의 정수이다.
출력
반딧불이 얻게 되는 최대 수익을 출력한다.
예제1
입력
5 2
9 9 2 3 5
3 4 5 1 2
1 1 7 7 3
4 7 3 8 5
2 2 3 4 1
출력
59
예제2
입력
6 3
1 2 3 4 5 3
1 6 4 5 1 2
7 3 8 2 1 1
2 1 6 7 3 4
3 1 4 4 4 4
5 6 7 1 1 1
출력
89
예제3
입력
3 1
2 2 4
4 1 5
2 3 5
출력
13
예제4
입력
4 2
5 5 1 1
1 5 5 1
1 1 5 5
5 5 1 1
출력
36
출처
CHCI 2009 National Competition #1 Seniors MISOLOVKE