Digging for Oil

The government of Siruseri has decided to auction off, to oil-development contractors, the land of Navaru province where crude oil is abundant. The whole area up for auction is divided into small blocks that form an $M \times N$ rectangular grid.

Siruseri's geological survey bureau has an estimate of the crude-oil content of each block; these estimates are given as a non-negative integer in each cell of the $M \times N$ grid.

To prevent monopolies, the government requires that each contractor may bid on exactly one contiguous $K \times K$ square of blocks.

The AoE Oil Association, made up of three contractors, wants to secure as much oil as possible by choosing three non-overlapping $K \times K$ square regions.

For example, for the grid in the sample input below, the best achievable total is $100$ when $K = 2$ and $208$ when $K = 3$.

Write a program that finds the maximum total estimated oil content the AoE Association can secure.

The first line contains three integers $M$, $N$, and $K$, where $M$ and $N$ are the numbers of rows and columns of the grid, and $K$ is the side length of the square region a contractor bids on. Each of the next $M$ lines contains the oil-content estimates of the $N$ blocks in one row, given as non-negative integers.

$K \le M$ and $K \le N$, and at least three non-overlapping $K \times K$ regions exist. Also $M, N \le 1500$, and every block's estimate is a non-negative integer less than $500$.

Print, on a single line, the maximum total estimated oil content the AoE Oil Association can secure.