Description

The Siruseri government has decided to auction off land in the oil-rich province of Navalur to private contractors for building oil wells. The land to be auctioned is a rectangular area divided into $M \times N$ blocks. The Siruseri Geological Survey has estimates of the oil reserves in Navalur. These are given as $M \times N$ positive integers, i.e., the estimated yield for each block.

To avoid monopoly, the government stipulates that each contractor may lease only one square region consisting of $K \times K$ adjacent blocks. The AoE Oil Consortium consists of three contractors. They want to choose three pairwise non-overlapping $K \times K$ regions so that the total yield is maximized.

For example, suppose the estimated yields are as follows:

1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 
1 8 8 8 8 8 1 1 1 
1 8 8 8 8 8 1 1 1 
1 8 8 8 8 8 1 1 1 
1 1 1 1 8 8 8 1 1 
1 1 1 1 1 1 8 8 8 
1 1 1 1 1 1 9 9 9 
1 1 1 1 1 1 9 9 9 

• If $K = 2$, the total yield the AoE company can get is $100$.
• If $K = 3$, the total yield the AoE company can get is $208$.

AoE hires you to write a program to compute the maximum possible sum of yields of the regions they can lease.

Input Format

The first line contains three positive integers $M$, $N$, $K$, where $M$ and $N$ are the numbers of rows and columns of the rectangle, and $K$ is the side length (in blocks) of each contractor’s square region. The next $M$ lines each contain $N$ positive integers giving the estimated yield for each block in that row.

Output Format

Output a single integer: the maximum possible total yield of the three leased regions.

9 9 3
1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 
1 8 8 8 8 8 1 1 1 
1 8 8 8 8 8 1 1 1 
1 8 8 8 8 8 1 1 1 
1 1 1 1 8 8 8 1 1 
1 1 1 1 1 1 8 8 8 
1 1 1 1 1 1 9 9 9 
1 1 1 1 1 1 9 9 9 

208

Hint

It is guaranteed that $K \le M$ and $K \le N$, and that there exist at least three pairwise disjoint $K \times K$ square regions.

For $30\%$ of the testdata, $M, N \le 12$. For all testdata, $M, N \le 1500$. The estimate for each block is a non-negative integer not exceeding $500$.

Translated by ChatGPT 5