K-Triangles

You are given an $n \times m$ matrix $A$ of integers and a positive integer $k$.

For a cell $(x_0, y_0)$ of $A$, the $k$-triangles centered at $(x_0, y_0)$ are defined as follows.

• If $1 \le x_0 \le n-k+1$ and $1 \le y_0 \le m-k+1$, then $T_0 = \{(x, y) : x \ge x_0, y \ge y_0, |x-x_0| + |y-y_0| < k\}$.
• If $k \le x_0 \le n$ and $1 \le y_0 \le m-k+1$, then $T_1 = \{(x, y) : x \le x_0, y \ge y_0, |x-x_0| + |y-y_0| < k\}$.
• If $k \le x_0 \le n$ and $k \le y_0 \le m$, then $T_2 = \{(x, y) : x \le x_0, y \le y_0, |x-x_0| + |y-y_0| < k\}$.
• If $1 \le x_0 \le n-k+1$ and $k \le y_0 \le m$, then $T_3 = \{(x, y) : x \ge x_0, y \le y_0, |x-x_0| + |y-y_0| < k\}$.

The cost of a $k$-triangle $T$ is $f(T) = \sum_{(x,y) \in T} A_{x,y}$.

Find the maximum possible total cost of two non-intersecting $k$-triangles. Formally, find $\max_{P \cup Q = \emptyset}{f(P) + f(Q)}$, where $P$ and $Q$ are some $k$-triangles.

The first line contains three space-separated integers $n$, $m$, and $k$ ($1 \le n, m, k \le 1500$). Each of the next $n$ lines contains $m$ space-separated integers. The $i$-th line contains $A_{i,1}, A_{i,2}, \dots, A_{i,m}$ ($-10^9 \le A_{i,j} \le 10^9$). It is guaranteed that there is at least one way to choose two non-intersecting $k$-triangles in the matrix.

Print a single integer: the maximum possible sum of costs of two non-intersecting $k$-triangles.

In the second example, the answer is made up of two $k$-triangles of type $T_1$ with centers at $(4, 1)$ and $(3, 3)$.