Statement

Ninetail is a fox girl. She studies in NFLS Class 8 Junior 3. She, Ookami and Doragon are friends.

One day, Ookami sent her a cake. Then she cut the cake into N*M grids. In $(i,j)$ grid, there are $A_{i,j}$ grapes.

Ninetail had a trianglar tooth. She could move her tooth to $(x,y)$ and eat the grid $(i,j)$ if $|x-i|+|y-j|\lt K,i\leq x$ where K is constant. Notice that she couldn't bite out of the cake because that really hurt. For example, a bite with K=2 looks like

XOX
O*X
XOX

*=tooth position(x,y) (in bite too)
O=in bite
X=out of bite

And when K=3

XXOX
XOOX
OO*X
XOOX
XXOX

The deliciousness of a bite at $(x,y)$ is defined as $\sum ^{(i,j)} A_{i,j}[|x-i|+|y-j|\lt K][i\leq x]$. Find the max deliciousness.

Note: [x]=1 when x is true. 0 otherwise

Input

First line contains N,M,K Then a matrix with N lines M columns

Output

The Answer

Example

[Input]
4 4 2
1 1 1 1
2 2 2 2
3 3 3 3
4 4 4 4
[Output]
12
[Explain]
Bite at (2,2) (2,3) (2,4) will have deliciousness 1+2+2+3=8
Bite at (3,2) (3,3) (3,4) will have deliciousness 2+3+3+4=12

Subtask

Subtask 1(10%): $1\leq N,M\leq 10$

Subtask 2(30%): $1\leq N,M\leq 100$

Subtask 3(60%): $1\leq N,M\leq 1000$

For all subtask, $1\leq K\leq min(M,\frac{N+1}{2}),0\leq A_{i,j}\leq 32767$