A Strip of Land

Time limit2sMemory limit128 MB

Summary

Given a U by V grid of heights, find the largest-area rectangle whose height range is at most C and whose width is at most 100.

Level: Hard8 of 10
Topics: Sliding window, Matrix, Two pointers, Brute force
Solved: No attempts yet

Problem

The residents of Dingilville want to choose a region of land on which to build an airport. They have a map of the terrain: a rectangular grid of unit squares. Each square is identified by a pair of coordinates $(x, y)$ , where $x$ is the horizontal (west–east) coordinate and $y$ is the vertical (south–north) coordinate. The map lists the height of every square.

Find a rectangular region of squares with the largest area (that is, the largest number of squares) such that

the height difference between the highest and the lowest square of the region is at most a given limit $C$ , and
the width of the region (the number of squares in the west–east direction) is at most $100$ .

Report the area of such a largest region.

Input

The first line contains three integers $U$ , $V$ , and $C$ .
Each of the next $V$ lines contains the heights $H_{xy}$ for $x = 1, \dots, U$ . More precisely, $H_{xy}$ is the $x$ -th number on the $(V - y + 2)$ -th input line, so the first data line holds the northernmost row ( $y = V$ ) and the last data line holds the southernmost row ( $y = 1$ ).

Output

Print a single integer: the largest possible area (number of squares) of a region that satisfies both conditions.

Constraints

$1 \le U \le 700$ and $1 \le V \le 700$ , where $U$ is the number of squares in the west–east direction and $V$ the number in the south–north direction.
$0 \le C \le 10$ .
$-30\,000 \le H_{xy} \le 30\,000$ , where $H_{xy}$ is the height of the square at coordinates $(x, y)$ , with $1 \le x \le U$ and $1 \le y \le V$ .
The southwest corner square of the map has coordinates $(1, 1)$ and the northeast corner has coordinates $(U, V)$ .

Examples3

Example 1

Input

10 15 4
41 40 41 38 39 39 40 42 40 40
39 40 43 40 36 37 35 39 42 42
44 41 39 40 38 40 41 38 35 37
38 38 33 39 36 37 32 36 38 40
39 40 39 39 39 40 40 41 43 41
39 40 41 38 39 38 39 39 39 42
36 39 39 39 39 40 39 41 40 41
31 37 36 41 41 40 39 41 40 40
40 40 40 42 41 40 39 39 39 39
42 40 44 40 38 40 39 39 37 41
41 41 40 39 39 40 41 40 39 40
47 46 49 43 43 41 41 40 39 42
42 41 41 39 40 39 42 40 42 42
41 44 49 43 46 41 42 41 42 42
45 40 42 42 46 42 44 40 42 41

Expected output

Example 2
Input
```
3 3 0
2 2 2
2 2 2
2 2 2
```
Expected output
```
9
```
Example 3
Input
```
1 1 0
5
```
Expected output
```
1
```