시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 3 3 3 100.000%

문제

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

For a given cell $(x_0, y_0)$ of matrix $A$, we define the following sets of cells as $k$-triangles with center $(x_0, y_0)$:

• $T_0 = {(x, y) : x \ge x_0, y \ge y_0, |x − x_0| + |y − y_0| < k}$ if $1 \le x_0 \le n − k + 1, 1 \le y_0 \le m − k + 1$;
• $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, 1 \le y_0 \le m − k + 1$;
• $T_2 = {(x, y) : x \le x_0, y \le y_0, |x − x_0| + |y − y_0| < k}$ if $k \le x_0 \le n, k \le y_0 \le m$;
• $T_3 = {(x, y) : x \ge x_0, y \le y_0, |x − x_0| + |y − y_0| < k}$ if $1 \le x_0 \le n − k + 1, k \le y_0 \le m$.

For a given $k$-triangle $T$, we define its cost $f(T) = \sum_{(x,y) \in T}{A_{x,y}}$.

Your task is to find the maximum possible total cost of any two non-intersecting $k$-triangles. Formally, you have to 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$, $k$ ($1 \le n, m, k \le 1500$).

Each of the next $n$ lines contains $m$ space-separated integers; the $i$-th line contains integers $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.

예제 입력 1

3 4 2
0 1 0 0
0 1 1 1
0 0 1 1


예제 출력 1

6


예제 입력 2

4 5 3
-5 -7 4 5 -3
-7 -5 8 0 -7
4 6 2 6 5
7 3 1 -7 7


예제 출력 2

39


힌트

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)$.