기름 파기

시루세리 정부는 원유가 많이 묻혀 있는 나바루 주의 땅을, 유전개발을 할 수 있는 개인사업자들에게 경매로 팔도록 결정하였다. 경매 처리할 전체 땅은 MⅹN 직사각형 격자 형태의 작은 구역으로 분할되었다. 

시루세리 정부의 지질측정국은 나바루 주 각 구역에 대한 원유 함유량 추정치 자료를 가지고 있다. 이 자료는 MⅹN 격자에 음이 아닌 정수로 작은 구역 별로 원유 함유량 추정치가 주어진다.

독점의 방지를 위하여, 정부는 어떤 계약자도 오직 하나의 KⅹK 규격의 정사각형 모양의 연속된 작은 구역들만 응찰 할 수 있도록 규정하였다. 

3개의 사업자로 구성된 AoE 기름협회는 가능한 가장 많은 양의 원유 확보를 위하여 3개의 위에 설명된 규격의 구역을 겹치지 않게 선택하려고 한다.

추정된 원유 함유량이 다음과 같이 주어졌다고 하자.

만일 K=2 라면, AoE 협회는 구역의 선택을 통하여 총합이 100 단위의 추정 함유량의 확보가 가능하며, K=3으로 주어질 경우 총합 208 단위의 추정 함유량의 확보가 가능하다. 

AoE는 당신을 고용하여, 그들이 차지할 수 있는 최대한의 추정 원유 함유량을 알아내는 프로그램을 작성하고자 한다.

첫 번째 줄에는 세 개의 정수 M, N, K가 주어지는데, M과 N은 각각 직사각형 격자의 행과 열 개수이고 K는 한 사업자가 입찰에 응할 수 있는 정사각형 구역 한 변의 크기이다. 다음 M개의 줄에는 각각 한 행에 해당하는 N 구역의 원유 함유량 추정치가 음이 아닌 정수로 주어 진다.

K ≤ M 또한 K ≤ N이고 최소 세 개의 겹치지 않는 KⅹK 구역이 존재한다. 또, M, N ≤ 1500이며, 각 구역의 원유 함유량의 추정치는 모두 음수가 아닌 정수이고, 500 보다 작다.

첫 줄에 AoE 기름 협회가 차지할 수 있는 최대 추정 원유 함유량을 출력한다.