2027 : Digging for Oil
Problem type : Batch
Time limit : 1.5 second(s)
Memory limit : 128 megabyte(s)

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 off has been divided up into an M x 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 x 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 x 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:
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.

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

Input format
The first line of the input contains three integers M, N and K, 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.

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

Test Data
You may assume that K <= M and K <= N and that at least three disjoint K x K blocks are available. In 30% of the inputs, M,N <= 12. In all inputs, M,N <= 1500. The estimated oil reserve for each plot is always non-negative and never exceeds 500.

Reference: Asia-Pacific Informatics Olympiad 2009

ตัวอย่างข้อมูลนำเข้า	ตัวอย่างข้อมูลส่งออก
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

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้