#include<deque>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
#include<sstream>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
bool fi(vector<pair<int,int> >& p,pair<int,int> q){
  int i;
  for(i=0;i<(int)p.size();++i){
    if(p[i].first>=q.first&&p[i].second>=q.second)
      break;
  }
  if(i<(int)p.size())
    return false;
  for(i=0;i<(int)p.size();++i){
    if((p[i].first<q.first||p[i].second<q.second)&&p[i].first<=q.first&&p[i].second<=q.second){
      p.erase(p.begin()+i);
      --i;
    }
  }
  p.push_back(q);
  return true;
}
int main(){
  int i,j,k,l,s;
  int w,h;
  while(cin>>w>>h,w||h){
    int f,m,o;
    cin>>f>>m>>o;
    int a[10][10];
    for(i=0;i<h;++i)
      for(j=0;j<w;++j)
	cin>>a[i][j];
    int d[10][10][10][51],e[10][10][10][51];
    memset(d,-1,sizeof(d));
    memset(e,-1,sizeof(e));
    vector<pair<int,int> > b[10][10][10],c[10][10][10];
    for(i=0;i<w;++i){
      if(o<=1)
	continue;
      if(a[0][i]<0){
	if(f+a[0][i]<0)
	  continue;
	d[i][i][i][o-1]=f+a[0][i];
	b[i][i][i].push_back(make_pair(f+a[0][i],o-1));
      }else{
	d[i][i][i][min(m,o-1+a[0][i])]=f;
	b[i][i][i].push_back(make_pair(f,min(m,o-1+a[0][i])));
      }
    }
    for(i=0;i<h-1;++i){
      bool h;
      do{
	h=true;
	for(j=0;j<w;++j){
	  for(k=0;k<=j;++k){
	    for(l=j;l<w;++l){
	      for(s=0;s<(int)b[j][k][l].size();++s){      
		if(b[j][k][l][s].second==1)
		  continue;
		if(j){
		  if(j==k){
		    if(a[i][j-1]<0){
		      if(b[j][k][l][s].first+a[i][j-1]>=0&&d[j-1][k-1][l][b[j][k][l][s].second-1]<b[j][k][l][s].first+a[i][j-1]){
			d[j-1][k-1][l][b[j][k][l][s].second-1]=b[j][k][l][s].first+a[i][j-1];
			if(fi(b[j-1][k-1][l],make_pair(b[j][k][l][s].first+a[i][j-1],b[j][k][l][s].second-1)))
			  h=false;
		      }
		    }else{
		      if(d[j-1][k-1][l][min(m,b[j][k][l][s].second-1+a[i][j-1])]<b[j][k][l][s].first){
			d[j-1][k-1][l][min(m,b[j][k][l][s].second-1+a[i][j-1])]=b[j][k][l][s].first;
			if(fi(b[j-1][k-1][l],make_pair(b[j][k][l][s].first,min(m,b[j][k][l][s].second-1+a[i][j-1]))))
			  h=false;
		      }
		    }
		  }else{
		    if(d[j-1][k][l][b[j][k][l][s].second-1]<b[j][k][l][s].first){
		      d[j-1][k][l][b[j][k][l][s].second-1]=b[j][k][l][s].first;
		      if(fi(b[j-1][k][l],make_pair(b[j][k][l][s].first,b[j][k][l][s].second-1)))
			h=false;
		    }
		  }
		}
		if(j<w-1){
		  if(j==l){
		    if(a[i][j+1]<0){
		      if(b[j][k][l][s].first+a[i][j+1]>=0&&d[j+1][k][l+1][b[j][k][l][s].second-1]<b[j][k][l][s].first+a[i][j+1]){
			d[j+1][k][l+1][b[j][k][l][s].second-1]=b[j][k][l][s].first+a[i][j+1];
			if(fi(b[j+1][k][l+1],make_pair(b[j][k][l][s].first+a[i][j+1],b[j][k][l][s].second-1)))
			  h=false;
		      }
		    }else{
		      if(d[j+1][k][l+1][min(m,b[j][k][l][s].second-1+a[i][j+1])]<b[j][k][l][s].first){
			d[j+1][k][l+1][min(m,b[j][k][l][s].second-1+a[i][j+1])]=b[j][k][l][s].first;
			if(fi(b[j+1][k][l+1],make_pair(b[j][k][l][s].first,min(m,b[j][k][l][s].second-1+a[i][j+1]))))
			  h=false;
		      }
		    }
		  }else{
		    if(d[j+1][k][l][b[j][k][l][s].second-1]<b[j][k][l][s].first){
		      d[j+1][k][l][b[j][k][l][s].second-1]=b[j][k][l][s].first;
		      if(fi(b[j+1][k][l],make_pair(b[j][k][l][s].first,b[j][k][l][s].second-1)))
			h=false;
		    }
		  }
		}
		if(a[i+1][j]<0){
		  if(b[j][k][l][s].first+a[i+1][j]>=0&&e[j][j][j][b[j][k][l][s].second-1]<b[j][k][l][s].first+a[i+1][j]){
		    e[j][j][j][b[j][k][l][s].second-1]=b[j][k][l][s].first+a[i+1][j];
		    fi(c[j][j][j],make_pair(b[j][k][l][s].first+a[i+1][j],b[j][k][l][s].second-1));
		  }
		}else{
		  if(e[j][j][j][min(m,b[j][k][l][s].second-1+a[i+1][j])]<b[j][k][l][s].first){
		    e[j][j][j][min(m,b[j][k][l][s].second-1+a[i+1][j])]=b[j][k][l][s].first;
		    fi(c[j][j][j],make_pair(b[j][k][l][s].first,min(m,b[j][k][l][s].second-1+a[i+1][j])));
		  }
		}
	      }
	      b[j][k][l].clear();
	    }
	  }
	}
      }while(!h);
      memcpy(d,e,sizeof(e));
      memset(e,-1,sizeof(e));
      for(j=0;j<w;++j){
	for(k=0;k<w;++k){
	  for(l=0;l<w;++l){
	    b[j][k][l]=c[j][k][l];
	    c[j][k][l].clear();
	  }
	}
      }
    }
    int mx=-1;
    for(i=0;i<w;++i)
      for(j=0;j<(int)b[i][i][i].size();++j)
	mx=max(mx,b[i][i][i][j].first);
    if(mx<0)
      cout<<"NA"<<endl;
    else
      cout<<f-mx<<endl;
  }
  return 0;
}

Measured memory_bytes: 1348