K-삼각형

정수로 이루어진 $n \times m$ 행렬 $A$와 양의 정수 $k$가 주어진다.

$A$의 셀 $(x_0, y_0)$를 중심으로 하는 $k$-삼각형은 다음과 같이 정의한다.

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

$k$-삼각형 $T$의 비용은 $f(T) = \sum_{(x,y) \in T} A_{x,y}$이다.

서로 겹치지 않는 두 $k$-삼각형의 비용 합이 최대가 되는 값을 구하라. 형식으로는 $\max_{P \cup Q = \emptyset}{f(P) + f(Q)}$이며, 여기서 $P$와 $Q$는 임의의 $k$-삼각형이다.

첫째 줄에 공백으로 구분된 정수 $n$, $m$, $k$가 주어진다 ($1 \le n, m, k \le 1500$). 이어지는 $n$개 줄의 $i$번째 줄에는 공백으로 구분된 정수 $m$개 $A_{i,1}, A_{i,2}, \dots, A_{i,m}$이 주어진다 ($-10^9 \le A_{i,j} \le 10^9$). 행렬에서 서로 겹치지 않는 두 $k$-삼각형을 고를 수 있는 방법이 적어도 하나 있음이 보장된다.

서로 겹치지 않는 두 $k$-삼각형 비용 합의 최댓값을 정수 하나로 출력한다.

두 번째 예제의 답은 중심이 $(4, 1)$과 $(3, 3)$인 두 $T_1$형 $k$-삼각형으로 이루어진다.