Building a Helipad

Problem Description

Little A has a terrain map of $M$ rows and $N$ columns, where the number $a_{ij}$ at row $i$, column $j$ is the altitude at coordinate $(i, j)$.

A helipad is a $3 \times 3$ region whose $9$ cells have a difference between the maximum and minimum altitude of at most $H$.

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

Input Format

The first line contains three positive integers $M$, $N$, and $H$, as described. The following $M$ lines: the $i$-th line contains $N$ integers $a_{i1}, a_{i2}, \dots, a_{iN}$, the altitudes at each coordinate. It is guaranteed that at least one helipad-suitable region exists.

Output Format

Output one line: the maximum altitude sum.

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 from row $3$ column $1$ to row $5$ column $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$, the minimum is $2$, the 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 answer is $40$.

Constraints

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