#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;
int dp[12][12][12][12][52];
int v[12][12][12][12][52];
int t[12][12];
struct wolf{
	int cost;
	int row;
	int col;
	int L;
	int R;
	int v;
	wolf(){}
	wolf(int a,int b,int c,int d,int e,int f){
		cost=a;row=b;col=c;L=d;R=e;v=f;
	}
};
inline bool operator<(const wolf&a,const wolf&b){
	if(a.cost!=b.cost)return a.cost>b.cost;
	return false;
}
int main(){
	int a,b;
	while(scanf("%d%d",&b,&a),a){
		int c,d,e;scanf("%d%d%d",&c,&d,&e);
		for(int i=0;i<a;i++)for(int j=0;j<b;j++)scanf("%d",&t[i][j]);
		for(int i=0;i<a;i++)for(int j=0;j<b;j++)
			for(int k=0;k<b;k++)for(int l=0;l<b;l++)
				for(int m=0;m<=d;m++)
					dp[i][j][k][l][m]=999999999;
		for(int i=0;i<a;i++)for(int j=0;j<b;j++)for(int k=0;k<b;k++)
			for(int l=0;l<b;l++)for(int m=0;m<=d;m++)
				v[i][j][k][l][m]=0;
		priority_queue<wolf>Q;
		if(e<=1){
			printf("NA\n");continue;
		}
		for(int i=0;i<b;i++){
			if(t[0][i]>0){
				dp[0][i][i][i][min(d,e-1+t[0][i])]=0;
				Q.push(wolf(0,0,i,i,i,min(d,e-1+t[0][i])));
			}else{
				dp[0][i][i][i][e-1]=-t[0][i];
				Q.push(wolf(-t[0][i],0,i,i,i,e-1));
			}
		}
		while(Q.size()){
			wolf at=Q.top();
			Q.pop();
			if(v[at.row][at.col][at.L][at.R][at.v])continue;
			v[at.row][at.col][at.L][at.R][at.v]=1;
			if(at.v==1)continue;
			if(at.col){
				if(at.col==at.L){
					if(t[at.row][at.col-1]>0){
						int tov=min(d,at.v-1+t[at.row][at.col-1]);
						if(!v[at.row][at.col-1][at.col-1][at.R][tov]&&dp[at.row][at.col-1][at.col-1][at.R][tov]>at.cost){
							dp[at.row][at.col-1][at.col-1][at.R][tov]=at.cost;
							Q.push(wolf(at.cost,at.row,at.col-1,at.col-1,at.R,tov));
						}
					}else{
						if(!v[at.row][at.col-1][at.col-1][at.R][at.v-1]&&dp[at.row][at.col-1][at.col-1][at.R][at.v-1]>at.cost-t[at.row][at.col-1]){
							dp[at.row][at.col-1][at.col-1][at.R][at.v-1]=at.cost-t[at.row][at.col-1];
							Q.push(wolf(at.cost-t[at.row][at.col-1],at.row,at.col-1,at.col-1,at.R,at.v-1));
						}
					}
				}else{
					if(!v[at.row][at.col-1][at.L][at.R][at.v-1]&&dp[at.row][at.col-1][at.L][at.R][at.v-1]>at.cost){
						dp[at.row][at.col-1][at.L][at.R][at.v-1]=at.cost;
						Q.push(wolf(at.cost,at.row,at.col-1,at.L,at.R,at.v-1));
					}
				}
			}
			if(at.col<b-1){
				if(at.col==at.R){
					if(t[at.row][at.col+1]>0){
						int tov=min(d,at.v-1+t[at.row][at.col+1]);
						if(!v[at.row][at.col+1][at.L][at.col+1][tov]&&dp[at.row][at.col+1][at.L][at.col+1][tov]>at.cost){
							dp[at.row][at.col+1][at.L][at.col+1][tov]=at.cost;
							Q.push(wolf(at.cost,at.row,at.col+1,at.L,at.col+1,tov));
						}
					}else{
						if(!v[at.row][at.col+1][at.L][at.col+1][at.v-1]&&dp[at.row][at.col+1][at.L][at.col+1][at.v-1]>at.cost-t[at.row][at.col+1]){
							dp[at.row][at.col+1][at.L][at.col+1][at.v-1]=at.cost-t[at.row][at.col+1];
							Q.push(wolf(at.cost-t[at.row][at.col+1],at.row,at.col+1,at.L,at.col+1,at.v-1));
						}
					}
				}else{
					if(!v[at.row][at.col+1][at.L][at.R][at.v-1]&&dp[at.row][at.col+1][at.L][at.R][at.v-1]>at.cost){
						dp[at.row][at.col+1][at.L][at.R][at.v-1]=at.cost;
						Q.push(wolf(at.cost,at.row,at.col+1,at.L,at.R,at.v-1));
					}
				}
			}
			if(at.row<a-1){
				if(t[at.row+1][at.col]>0){
					int tov=min(d,at.v-1+t[at.row+1][at.col]);
					if(!v[at.row+1][at.col][at.col][at.col][tov]&&dp[at.row+1][at.col][at.col][at.col][tov]>at.cost){
						dp[at.row+1][at.col][at.col][at.col][tov]=at.cost;
						Q.push(wolf(at.cost,at.row+1,at.col,at.col,at.col,tov));
					}
				}else{
					if(!v[at.row+1][at.col][at.col][at.col][at.v-1]&&dp[at.row+1][at.col][at.col][at.col][at.v-1]>at.cost-t[at.row+1][at.col]){
						dp[at.row+1][at.col][at.col][at.col][at.v-1]=at.cost-t[at.row+1][at.col];
						Q.push(wolf(at.cost-t[at.row+1][at.col],at.row+1,at.col,at.col,at.col,at.v-1));
					}
				}
			}
		}
		int ret=999999999;
		for(int i=0;i<b;i++){
			for(int j=0;j<b;j++)for(int k=0;k<b;k++)
				for(int l=1;l<=d;l++)ret=min(ret,dp[a-1][i][j][k][l]);
		}
		if(ret>c){
			printf("NA\n");
		}else printf("%d\n",ret);
	}
}

Measured memory_bytes: 8976