문제
나돌석은 돌을 채취하는 채석회사를 운영한다. 최근 Marble 왕국으로부터 N * N 넓이의 지역에 대한 채석 허가를 얻었다. 나름 좋은 조건에 채석계약을 채결하였는데 계약서에 따르면 다음 두 가지를 꼭 준수해야 한다.
채석장을 정방형의 그리드 모양으로 나누었을 때, 1. 각 행마다 연속한 K구간을 채석한다. 2. 이웃한 행의 같은 열이 채석되지 않도록 한다.
N=5이고 K=2인 경우를 예로 들어 살펴보자면 아래 그림들 중에 입력 예를 설명하고 있는 그림1만 가능한 경우가 된다. 그림2는 조건 1을 어겼으며 그림3은 조건 2를 어긴 경우이다.
사업가답게 나돌석은 N * N구간을 단위크기로 나누어 각 격자 크기의 돌에 대한 상품성을 조사한 가격표를 만들었다. 이제 채석을 하려고 한다. 나돌석은 최대 얼마의 수익을 얻을 수 있을까?
입력
첫 행에 채석장의 크기 N과 연속한 구간 크기 K가 공백으로 구분되어 입력된다. (2 <= N <= 1000, 1<= K <= N/2)
다음 행부터 N개의 행에 걸쳐 채석장의 정보가 공백으로 구분되어 입력된다.
입력되는 각 격자의 숫자는 1이상 100,000미만의 정수이다.
출력
나돌석이 얻게 되는 최대 수익을 출력한다.
예제
5 2
1 2 3 4 5
1 1 7 7 3
9 9 2 3 5
4 7 3 8 5
2 2 3 4 1
53
출처
2017 ICT Award KOREA
로그인해야 코드를 작성할 수 있어요.