题目描述

工程师 Mira 正在分析一张带权网格。给定一个 $n\times m$ 的整数矩阵 $A$ 和一个正整数 $k$。

对于矩阵中的一个格子 $(x_0,y_0)$，可以定义四种以它为中心的 $k$-三角形区域。

第一种：

$$T_0=\{(x,y):x\ge x_0,\ y\ge y_0,\ |x-x_0|+|y-y_0|<k\},$$

要求

$$1\le x_0\le n-k+1,\qquad 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,\qquad 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\},$$

要求

$$k\le x_0\le n,\qquad 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\},$$

要求

$$1\le x_0\le n-k+1,\qquad k\le y_0\le m.$$

对于任意一个 $k$-三角形 $T$，定义它的代价为其中所有格子的权值之和：

$$f(T)=\sum_{(x,y)\in T} A_{x,y}.$$

请你选择两个互不相交的 $k$-三角形 $P,Q$，最大化

$$f(P)+f(Q).$$

这里互不相交表示两个区域没有公共格子。

输入格式

第一行包含三个整数 $n,m,k$。

接下来 $n$ 行，每行包含 $m$ 个整数。第 $i$ 行的第 $j$ 个整数为 $A_{i,j}$。

输出格式

输出一行一个整数，表示两个互不相交的 $k$-三角形总代价的最大值。

数据范围

• $1\le n,m,k\le 1500$；
• $-10^9\le A_{i,j}\le 10^9$；
• 保证至少存在一种方式选择两个互不相交的 $k$-三角形。

样例 1

输入

3 4 2
0 1 0 0
0 1 1 1
0 0 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

输出

39

解释

样例 2 中，最优答案可以由两个类型为 $T_1$ 的 $k$-三角形得到，它们的中心分别为 $(4,1)$ 和 $(3,3)$。