Asia-Pacific Informatics Olympiad 2009

Problem 1: Digging for Oil

The Government of Siruseri has decided to auction off land in its oil-rich Navalur province to private contractors to set up oil wells. The entire area that is being auctioned has been divided up into an M × N rectangular grid of smaller plots.

The Geological Survey of Siruseri has data on the estimated oil reserves in Navalur. This information is published as an M × N grid of non-negative integers, giving the estimated reserves in each of the plots.

In order to prevent a monopoly, the government has ruled that any contractor may bid for only one K × K square block of contiguous plots.

The AoE oil cartel consists of a group of 3 colluding contractors who would like to choose 3 disjoint blocks so as to maximize their total yield. Suppose that the estimated oil reserves are as described below:

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 AoE cartel can take over plots with a combined estimated reserve of 100 units, whereas if K = 3 they can take over plots with a combined estimated reserve of 208 units.

AoE has hired you to write a program to help them identify the maximum estimated oil reserves that they can take over.

Input

The first line of the input contains three integers M (M ≤ 1500), N (N ≤ 1500), and K (KM,N), where M and N are the number of rows and columns in the rectangular grid of plots and K is the size of the square block for which bids can be made. The next M lines contain N non-negative integers—each line describes the estimated oil reserves for one row of plots. The estimated oil reserve for a plot never exceeds 500, and it will always be possible to select at least three distinct K × K plots.

Output

A single line with a single integer indicating the maximum estimated oil reserves that can be taken over by the AoE cartel.

Sample Input

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

Sample Output

208

Note on grading

In 30% of the test cases, M and N will not exceed 12.

All Submissions
Best Solutions


Point Value: 30 (partial)
Time Limit: 3.00s
Memory Limit: 128M
Added: Jul 21, 2009

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

It's quiet in here...