Soma alternada de submatrizes

Seja $$B_{R\times S} = \left[ \begin{array}{ccccc} b_{11} & b_{12} & b_{13} & \ldots & b_{1S} \\ b_{21} & b_{12} & b_{23} & \ldots & b_{2S} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ b_{R1} & b_{R2} & b_{R3} & \ldots & b_{RS} \\ \end{array} \right]$$ uma matriz. Definimos a matriz alternada $\bar{B}$ como $$\bar{B}_{R\times S} = \left[ \begin{array}{ccccc} b_{11} & -b_{12} & b_{13} & \ldots & (-1)^{1+S}b_{1S} \\ -b_{21} & b_{12} & -b_{23} & \ldots & (-1)^{2+S}b_{2S} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ (-1)^{R+1}b_{R1} & (-1)^{R+2}b_{R2} & (-1)^{R+3}b_{R3} & \ldots & (-1)^{R+S}b_{RS} \\ \end{array} \right]$$ e a soma dos elementos de uma matriz $C_{M\times N}$ como $$S(C) = \sum_{i = 1}^M\sum_{j = 1}^N c_{ij}$$

Dada uma matriz $A_{H\times W}$, determine a maior soma dos elementos possível dentre as matrizes alternadas de todas as submatrizes de $A$ de dimensões $K\times K$.

Entrada

A primeira linha da entrada contém os valores dos inteiros $H, W, K$ $(1\leq H, W\leq 2\times 10^3, 1\leq K\leq \min(H, W))$, separados por um espaço em branco.

As $H$ linhas contém, cada uma, $W$ inteiros $a_{i1}, a_{i2}, \ldots, a_{iW}$, $(-10^5\leq a_{ij}\leq 10^5)$, separados por um espaço em branco, representando a $i$-ésima linha da matriz $A$.

Saída

Imprima, em uma linha, a maior soma dos elementos dentre todas as matrizes alternadas das submatrizes de dimensões $K\times K$ da matriz $A$.

Exemplo de entrada 1

2 3 2
1 -1 2
3 2 7

Exemplo de saída 1

2

Explicação do exemplo 1: No primeiro caso, há duas submatrizes $2\times 2$ de $A$, a saber $$B_1 = \left[ \begin{array}{cc} 1 & -1 \\ 3 & 2 \end{array} \right]$$ e $$B_2 = \left[ \begin{array}{cc} -1 & 2 \\ 2 & 7 \end{array} \right]$$

As matrizes alternadas destas matrizes são $$\bar{B_1} = \left[ \begin{array}{cc} 1 & 1 \\ -3 & 2 \end{array} \right]$$ e $$\bar{B_2} = \left[ \begin{array}{cc} -1 & -2 \\ -2 & 7 \end{array} \right],$$

de modo que $S(\bar{B_1}) = 1 + 1 - 3 + 2 = 1$ e $S(\bar{B_2}) = 7 - 1 - 2 - 2 = 2$. Portanto, a maior soma dos elementos possível dentre as matrizes $\bar{B_1}$ e $\bar{B_2}$ é igual a $2$.

Exemplo de entrada 2

3 3 3
1 -1 2
0 1 3
-2 1 2

Exemplo de saída 2

1

Exemplo de entrada 3

4 3 1
1 -2 4
-3 0 1
2 2 2
-3 5 -1

Exemplo de saída 3

5