Maximizing Oil Reserves from Non-Overlapping Regions

The government of Siruseri has decided to auction off a rectangular parcel of land in the oil-rich province of Navalur. The land is divided into an \(M \times N\) grid, where each cell contains a positive integer representing the estimated oil reserves in that plot.

To prevent monopolies, the government rules that each contractor may only bid on a contiguous \(K\times K\) square block of land. The AoE Oil Consortium, composed of three contractors, wishes to select three non-overlapping \(K\times K\) blocks such that the total sum of oil reserves in the chosen regions is maximized.

Two \(K\times K\) regions with top-left corners at \((r_1, c_1)\) and \((r_2, c_2)\) are considered non-overlapping if they do not share any common cell. In other words, they are disjoint if at least one of the following conditions holds:

• \(r_1 + K \le r_2\) or \(r_2 + K \le r_1\), or
• \(c_1 + K \le c_2\) or \(c_2 + K \le c_1\).

Your task is to help the AoE Oil Consortium compute the maximum possible total oil reserve sum that can be achieved by choosing three non-overlapping \(K\times K\) blocks.

Example:

For the following 9x9 grid of oil reserve estimates:
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 maximum total oil reserve sum is 100.
If (K = 3), the maximum total oil reserve sum is 208.
</pre>

inputFormat
The first line of input contains three integers \(M\), \(N\), and \(K\) where \(M\) and \(N\) are the dimensions of the grid and \(K\) denotes the size of each square block to be chosen. The following \(M\) lines each contain \(N\) positive integers, representing the oil reserve estimates for each cell of the grid.
outputFormat
Output a single integer representing the maximum total oil reserve sum achievable by selecting three non-overlapping \(K\times K\) regions.
sample
3 3 1
1 2 3
4 5 6
7 8 9
24