문제
다이아몬드 광산을 운영하는 반딧불은 지난 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
입력
52
99235
34512
11773
47385
22341
출력
59
예제2
입력
63
123453
164512
738211
216734
314444
567111
출력
89
예제3
입력
31
224
415
235
출력
13
예제4
입력
42
5511
1551
1155
5511
출력
36
출처
CHCI 2009 National Competition #1 Seniors MISOLOVKE