#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <sstream>
#include <cstring>
#include <cstdlib>

using namespace std;

#define ALL(c) c.begin(),c.end()
#define RALL(c) c.rbegin(),c.rend()
#define SORT(x) sort((x).begin(),(x).end())
#define REP(i,x,y) for(int i=(x);i<(y);++i)
#define MP(a,b) make_pair((a),(b))
#define F_ first
#define S_ second
#define debug(x) #x << "=" << (x)
 
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define dump(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define dump(x)
#endif

typedef long long int lli;
typedef pair<int,int> pii;
//template<typename T> using vec=std::vector<T>;

const int INF=1<<30;
const long long int INF_=1LL<<58;
const double EPS=1e-9;
const int dx[]={1,0,-1},dy[]={0,1,0};

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
	os << "[";
	for (const auto &v : vec) {
		os << v << ",";
	}
	os << "]";
	return os;
}

struct State{
	int x,y,d,o,s;
	State(int a,int b,int h,int e,int g):x(b),y(a),d(h),o(e),s(g){}
	bool operator>(const State& s)const{
		return d>s.d;
	}
};

int W,H,f,m,o,c[10][10],d[10][10][51][1<<10],ans;

void Solve(){
	fill_n((int*)d,10*10*51*(1<<10),INF);
	ans=INF;
	priority_queue<State,vector<State>,greater<State>> que;
	REP(x,0,W){
		int cost=0,oxy=o-1;
		if(oxy<=0) continue;
		if(c[0][x]<0) cost=-c[0][x];
		else oxy=min(m,oxy+c[0][x]);
		if(cost>f||oxy<=0) continue;
		d[0][x][oxy][1<<x]=cost;
		que.push(State(0,x,cost,oxy,1<<x));
	}
	while(!que.empty()){
		State v=que.top();
		que.pop();
		int vy=v.y,vx=v.x,vd=v.d,vo=v.o,vs=v.s;
		if(vy==H-1) ans=min(ans,d[vy][vx][vo][vs]);
		if(d[vy][vx][vo][vs]<vd||vo<=1) continue;
		REP(i,0,3){
			int ny=vy+dy[i],nx=vx+dx[i];
			if(ny<0||H<=ny||nx<0||W<=nx) continue;
			int cost=0,no=vo-1,ns=vs|(1<<nx);
			if(ny!=vy||((vs>>nx)&1)==0){
				if(c[ny][nx]<0) cost=-c[ny][nx];
				else no=min(m,no+c[ny][nx]);
			}
			if(ny!=vy) ns=1<<nx;
			if(vd+cost<d[ny][nx][no][ns]&&vd+cost<=f){
				d[ny][nx][no][ns]=vd+cost;
				que.push(State(ny,nx,d[ny][nx][no][ns],no,ns));
			}
		}
	}
}

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	while(true){
		cin >> W >> H;
		if(W==0&&H==0) break;
		cin >> f >> m >> o;
		REP(y,0,H) REP(x,0,W) cin >> c[y][x];
		Solve();
		if(ans==INF) cout << "NA";
		else cout << ans;
		cout << endl;
	}
	return 0;
}