#include <string.h>#include <stdio.h>#include <iostream>#include <algorithm>using namespace std;#define maxn 109int T,X,Y,R;int g[maxn][maxn],f[maxn][maxn][maxn];int lkX[maxn][maxn][maxn],lknX[maxn][maxn];int lkY[maxn][maxn][maxn],lknY[maxn][maxn];int C[maxn][maxn][maxn],V[10009];inline bool cmp(int n1,int n2){return n1>n2;}void init(){for(int x=1;x<=X;x++)for(int y=1;y<=Y;y++)for(int t=0;t<=T+1;t++)lkX[x][y][t]=lkY[x][y][t]=0;int t;for(int x=1;x<=X;x++)for(int y=1;y<=Y;y++){lknX[x][y]=0;lknY[x][y]=0;lkX[x][y][0]=0;lkY[x][y][0]=0;if(y-R>0){for(int i=x-R;i<=x+R;i++){if(i>=1&&i<=X&&g[i][y-R]!=0){t=++lknY[x][y];lkY[x][y][t]=g[i][y-R];}}}if(x-R>0){for(int j=y-R;j<=y+R;j++){if(j>=1&&j<=Y&&g[x-R][j]!=0){t=++lknX[x][y];lkX[x][y][t]=g[x-R][j];}}}sort(lkX[x][y]+1,lkX[x][y]+1+lknX[x][y],cmp);sort(lkY[x][y]+1,lkY[x][y]+1+lknY[x][y],cmp);}for(int x=1;x<=X;x++){for(int y=1;y<=Y;y++){int cnt=0;for(int i=x-R;i<=x+R;i++)for(int j=y-R;j<=y+R;j++){if(i>=1&&i<=X&&j>=1&&j<=Y)V[++cnt]=g[i][j];}sort(V+1,V+1+cnt,cmp);C[x][y][0]=0;for(int k=1;k<=cnt;k++)C[x][y][k]=C[x][y][k-1]+V[k];for(int k=cnt+1;k<=T+1;k++)C[x][y][k]=C[x][y][cnt];}}}#define Inf 1000000000void solve(){for(int i=1;i<=X;i++){for(int j=1;j<=Y;j++)for(int k=0;k<=T+1;k++)f[i][j][k]=-Inf;}f[1][1][0]=0;init();int sum,cost;for(int t=0;t<=T;t++){for(int x=1;x<=X;x++){for(int y=1;y<=Y;y++){if(g[x][y]!=0)continue;if(f[x][y][t]<0)continue;cost=f[x][y][t];if(y!=Y&&g[x][y+1]==0){sum=0;for(int k=0;t+1+k<=T+1;k++){sum+=lkY[x][y][k];f[x][y+1][t+1+k]=max(f[x][y+1][t+1+k],sum+cost);}}if(x!=X&&g[x+1][y]==0){sum=0;for(int k=0;t+1+k<=T+1;k++){sum+=lkX[x][y][k];f[x+1][y][t+1+k]=max(f[x+1][y][t+1+k],sum+cost);}}}}}int maxv=0;for(int t=0;t<=T+1;t++){for(int x=1;x<=X;x++){for(int y=1;y<=Y;y++)maxv=max(maxv,f[x][y][t]+C[x][y][T+1-t]);}}printf("%dn",maxv);}int main(){for(;;){if(scanf("%d",&T)==EOF)break;T--;scanf("%d%d",&Y,&X);int sum=0;for(int y=Y;y>=1;y--)for(int x=1;x<=X;x++){scanf("%d",&g[x][y]);sum+=g[x][y];if(sum>Inf||g[x][y]<0)while(1)printf("11111111n");}scanf("%d",&R);solve();}return 0;}
