시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 4 4 4 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)\).