#include <bits/stdc++.h>
using namespace std;
typedef tuple<int, int, int, int, int, int> Tp;
#define at(t, i) get<i>(t)
const int INF = 1 << 28;
const int dy[] = {0, 0, 1};
const int dx[] = {-1, 1, 0};

int H, W, F, M, O;
int cost[10][10];
int o2[10][10];
int dist[10][10][10][10][51];

bool ok(int x)
{
	return x >= 0 && x < W;
}

int solve()
{
	if (O <= 1) return INF;
	
	priority_queue<Tp, vector<Tp>, greater<Tp>> pq;
	
	for (int i = 0; i < W; i++){
		pq.push( Tp(cost[0][i], 0, i, i, i, min(O + o2[0][i] - 1, M)) );
	}
	
	while (pq.size()){
		Tp tp = pq.top(); pq.pop();
		int y = at(tp, 1);
		int x = at(tp, 2);
		int lx = at(tp, 3);
		int rx = at(tp, 4);
		int o = at(tp, 5);
		int sum = at(tp, 0);
		if (dist[y][x][lx][rx][o] < sum) continue;
		if (y == H - 1) return sum;
		if (o <= 1) continue;
		
		for (int dir = 0; dir < 2; dir++){
			int ny = y;
			int nx = x + dx[dir];
			if (!ok(nx)) continue;
			int nlx = min(nx, lx);
			int nrx = max(nx, rx);
			int no = o - 1;
			int nsum = sum;
			if (nx < lx || rx < nx){
				no = min(no + o2[y][nx], M);
				nsum += cost[y][nx];
			}
			if (dist[ny][nx][nlx][nrx][no] > nsum){
				dist[ny][nx][nlx][nrx][no] = nsum;
				pq.push( Tp(nsum, ny, nx, nlx, nrx, no) );
			}
		}
		
		int ny = y + 1;
		int nx = x;
		int nlx = x;
		int nrx = x;
		int no = min(o - 1 + o2[ny][nx], M);
		int nsum = sum + cost[ny][nx];
		if (dist[ny][nx][nlx][nrx][no] > nsum){
			dist[ny][nx][nlx][nrx][no] = nsum;
			pq.push( Tp(nsum, ny, nx, nlx, nrx, no) );
		}
	}
	
	return INF;
}

int main()
{
	while (scanf("%d %d", &W, &H), W){
		scanf("%d %d %d", &F, &M, &O);
		
		fill_n(*cost, 100, 0);
		fill_n(*o2, 100, 0);
		fill_n(****dist, 510000, INF);
		
		for (int i = 0; i < H; i++){
			for (int j = 0; j < W; j++){
				int g;
				scanf("%d", &g);
				if (g < 0) cost[i][j] = -g;
				else o2[i][j] = g;
			}
		}
		
		int res = solve();
		if (res <= F) printf("%d\n", res);
		else puts("NA");
	}
}