#include <iostream>
#include <queue>
using namespace std;
typedef long long int llf;
typedef pair<int,int> pr;
typedef pair<pr,pr> ppr;
typedef pair<pr,ppr> pppr;
const int INF=2<<26;
int DP[13][13][13][13][60]={},maps[11][11]={};
int W,H;
pppr pf(int a,int ab,int b,int c,int d,int e){
	return pppr(pr(a,ab),ppr(pr(b,c),pr(d,e)));
}
int money(int nx,int ny,int sx,int ex){
	if(nx<sx || nx>ex ||(nx==ex && ex==sx))
		if(nx>=0 && nx<W && ny<H && ny>=0 && maps[ny][nx]<0)
			return -maps[ny][nx];
	return 0;
}
int hydro(int nx,int ny,int sx,int ex){
	if(nx<sx || nx>ex ||(nx==ex && ex==sx))	
		if(nx>=0 && nx<W && ny<H && ny>=0&& maps[ny][nx]>=0)
			return maps[ny][nx];
	return 0;
}
int main() {
	// your code goes here
	while(cin >> W >> H && W!=0){
		int f=0,m=0,o=0,ans=INF;
		cin >> f >> m >> o;
		for(int i=0;i<11;i++)
			for(int j=0;j<11;j++)
				maps[i][j]=-INF;
		for(int i=0;i<H;i++)
			for(int j=0;j<W;j++)
				cin >> maps[i][j];
		for(int i=0;i<13;i++)
			for(int j=0;j<13;j++)
				for(int k=0;k<13;k++)
					for(int l=0;l<13;l++)
						for(int h=0;h<60;h++)
							DP[i][j][k][l][h]=INF;
		priority_queue<pppr,vector<pppr> > qu;
		if(o<=1){
			cout << "NA" << endl;
			continue;
		}
		for(int i=0;i<W;i++)
		DP[i][i][i][0][min(m,hydro(i,0,i,i)+o)-1]=money(i,0,i,i);
		for(int i=0;i<=H;i++){
			for(int j=0;j<W;j++)
				for(int k=m;k>=0;k--)
					if( DP[j][j][j][i][k]<DP[j][j][j][i][k+1])
						qu.push(pf(i,DP[j][j][j][i][k],k,j,j,j));
					else
						DP[j][j][j][i][k]=DP[j][j][j][i][k+1];
		while(!qu.empty()){
			int ab=qu.top().first.second,y=qu.top().first.first,hy=qu.top().second.first.first;
			int sx=qu.top().second.second.first,ex=qu.top().second.second.second,nx=qu.top().second.first.second,mo=DP[nx][sx][ex][y][hy];
			qu.pop();
			if(y>=H){
				ans=min(ans,mo);
				continue;
			}
			if(DP[nx][sx][ex][y][hy]==DP[nx][sx][ex][y][hy+2]) continue;
			if(mo!=ab) continue;
			if(hy==0) continue;
			int nh=min(m,hy+hydro(nx-1,y,sx,ex)-1),price=0;
			price=mo+money(nx-1,y,sx,ex);
			if(hy!=1 && nx>0 && DP[nx-1][sx-(nx==sx)][ex][y][nh]>price){
				DP[nx-1][sx-(nx==sx)][ex][y][nh]=price;
				qu.push(pf(y,price,nh,nx-1,sx-(nx==sx),ex));
			}
			nh=min(m,hy+hydro(nx+1,y,sx,ex)-1);
			price=mo+money(nx+1,y,sx,ex);
			if(hy!=1 && nx+1<W && DP[nx+1][sx][ex+(nx==ex)][y][nh]>price){
				DP[nx+1][sx][ex+(nx==ex)][y][nh]=price;
				qu.push(pf(y,price,nh,nx+1,sx,ex+(nx==ex)));
			}
			nh=min(m,hy+hydro(nx,y+1,nx,nx)-1);
			price=mo+money(nx,y+1,nx,nx);
			if(hy!=1 || y==H-1)
			DP[nx][nx][nx][y+1][nh]=min(DP[nx][nx][nx][y+1][nh],price);
		}
		}
		if(ans>f)
			cout <<"NA"<<endl;
		else
			cout << ans <<endl;
	}
	return 0;
}