#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

struct Info{
	Info(){
		row = col = oxyzen = cost = 0;
	}

	Info(int arg_row,int arg_col,int arg_oxyzen,int arg_cost){
		row = arg_row;
		col = arg_col;
		oxyzen = arg_oxyzen;
		cost = arg_cost;
	}

	int row,col,oxyzen,cost;
	bool visited[10][10];
};

int H,W,diff_row[3] = {0,0,1},diff_col[3] = {-1,1,0};
int min_cost[10][10][51];
int map[10][10];

bool rangeCheck(int row,int col){
	if(row >= 0 && row <= H-1 && col >= 0 && col <= W-1)return true;
	else{
		return false;
	}
}

void func(){

	int budget,Limit,first_oxyzen;

	scanf("%d %d %d",&budget,&Limit,&first_oxyzen);

	for(int i = 0; i < H; i++){
		for(int k = 0; k < W; k++){
			scanf("%d",&map[i][k]);
		}
	}

	if(first_oxyzen == 1){
		printf("NA\n");
		return;
	}

	queue<Info> Q;

	int minimum = BIG_NUM;
	int next_row,next_col;


	for(int start_col = 0; start_col < W; start_col++){

		for(int row = 0; row <= H-1; row++){
			for(int col = 0; col <= W-1; col++){
				for(int oxy = 0; oxy <= Limit; oxy++){
					min_cost[row][col][oxy] = BIG_NUM;
				}
			}
		}

		Info first;
		for(int row = 0; row < H; row++){
			for(int col = 0; col < W; col++){
				first.visited[row][col] = false;
			}
		}

		first.oxyzen = first_oxyzen-1;
		first.cost = 0;
		first.row = 0;
		first.col = start_col;
		first.visited[0][start_col] = true;

		if(map[0][start_col] > 0){
			first.oxyzen = min(first.oxyzen+map[0][start_col],Limit);

		}else{
			first.cost += abs(map[0][start_col]);
			if(first.cost > budget){
				continue;
			}
		}

		min_cost[0][start_col][first.oxyzen] = first.cost;

		Q.push(first);

		while(!Q.empty()){

			if(Q.front().row == H-1){
				Q.pop();
			}else if(Q.front().cost > min_cost[Q.front().row][Q.front().col][Q.front().oxyzen] || Q.front().oxyzen == 1){
				Q.pop();
			}else{

				for(int i = 0; i < 3; i++){
					next_row = Q.front().row + diff_row[i];
					next_col = Q.front().col + diff_col[i];

					if(!rangeCheck(next_row,next_col))continue;

					Info next_info;
					next_info.row = next_row;
					next_info.col = next_col;
					next_info.oxyzen = Q.front().oxyzen-1;
					next_info.cost = Q.front().cost;

					for(int row = 0; row < H; row++){
						for(int col = 0; col < W; col++){
							next_info.visited[row][col] = Q.front().visited[row][col];
						}
					}

					if(map[next_row][next_col] > 0 && next_info.visited[next_row][next_col] == false){
						next_info.oxyzen = min(next_info.oxyzen+map[next_row][next_col],Limit);
					}else{
						if(next_info.visited[next_row][next_col] == false){
							next_info.cost += abs(map[next_row][next_col]);
							if(next_info.cost > budget){
								continue;
							}
						}
					}

					next_info.visited[next_row][next_col] = true;

					if(min_cost[next_row][next_col][next_info.oxyzen] > next_info.cost){
						min_cost[next_row][next_col][next_info.oxyzen] = next_info.cost;
						Q.push(next_info);
					}
				}
				Q.pop();
			}
		}

		for(int col = 0; col < W; col++){
			for(int oxy = 0; oxy <= Limit; oxy++){
				minimum = min(minimum,min_cost[H-1][col][oxy]);
			}
		}
	}

	if(minimum == BIG_NUM){
		printf("NA\n");
	}else{
		printf("%d\n",minimum);
	}

}

int main(){

	while(true){
		scanf("%d %d",&W,&H);
		if(W == 0 && H == 0)break;

		func();
	}
	return 0;
}

Measured memory_bytes: 3140