Building a Helipad

Problem Description

Xiao A has a terrain map with $M$ rows and $N$ columns, where the number $a_{ij}$ at row $i$, column $j$ represents the altitude at coordinates $(i, j)$.

A helipad is a $3 \times 3$ region whose $9$ points have a maximum-to-minimum altitude difference of at most $H$.

Xiao A asks you to compute, among all regions suitable for building a helipad, the maximum possible sum of the altitudes of the $9$ points inside the region.

Input Format

The first line contains three positive integers $M, N, H$, as described.

The following $M$ lines: the $i$-th line contains $N$ integers $a_{i1}, a_{i2}, \dots, a_{iN}$, the altitudes at coordinates $(i, j)$.

It is guaranteed that at least one region suitable for building a helipad exists.

Output Format

Output one line containing the maximum sum of altitudes.

Sample Input

5 5 3
5 5 5 5 5
5 1 5 1 5
5 5 5 5 5
5 2 5 2 5
3 5 5 5 2

Sample Output

40

Sample Explanation

Among all $3 \times 3$ regions, the one spanning rows $3$ to $5$ and columns $1$ to $3$ satisfies the condition. Its $9$ altitudes are:

• Row 3: $5, 5, 5$;
• Row 4: $5, 2, 5$;
• Row 5: $3, 5, 5$.

Their sum is $5 + 5 + 5 + 5 + 2 + 5 + 3 + 5 + 5 = 40$. The maximum altitude in the region is $5$ and the minimum is $2$, so the altitude difference is $3$, which does not exceed $H = 3$. It can be verified that this is the largest altitude sum among all valid regions, so the output is $40$.

Constraints

For all test cases, $1 \le M, N \le 10^3$ and $1 \le H, a_{ij} \le 10^5$ are guaranteed.