IOI 99

[kpo]

Hi,
I can't solve this problem, it's for IOI 1999.
The time limit is 130 s and space limit is 600k


A STRIP OF LAND

PROBLEM

The residents of Dingilville are trying to locate a region to build an airport. The map of the land is at hand. The map is a rectangular grid of unit squares, each identified by a pair of coordinates (x,y), where x is the horizontal (west-east) and y is the vertical (south-north) coordinate. The height of every square is shown on the map.

Your task is to find a rectangular region of squares with the largest area (i.e. a rectangular region consisting of the largest number of squares) such that

the height difference between the highest and the lowest squares of the region is less than or equal to a given limit C, and
the width (i.e. the number of squares along the west-east direction) of the region is at most 100.
In case there is more than one such region you are required to report only one of them.



ASSUMPTIONS

1 <= U <=700, 1 <= V <=700 where U and V designate the dimensions of the map. More specifically, U is the number of squares in the west-east direction, and V, in the south-north direction.
0 <= C <= 10
-30,000 <= Hxy <= 30,000 where the integer Hxy is the height of the square at coordinates (x, y), 1 <= x <= U, 1 <= y <= V.
The southwest corner square of the map has the coordinates (1,1) and the northeast corner has the coordinates (U,V).


INPUT

The input is a text file named land.inp.

The first line contains three integers: U, V and C.
Each of the following V lines contains the integers Hxy for x = 1,