#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <set>

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,j) FOR(i,0,j)
#define mp std::make_pair

typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int,int> P;
typedef std::pair<int,std::pair<P,int>> State;

const int INF = 1001001001;

// S N E W(南北東西)
const int dx[3] = {-1, 0, 1}, dy[3] = {0, 1, 0};

int W, H, F, M, O;
int cell[11][11], d[11][11][51], dp[11][11][51];

int rec(int x, int y, int oxygen){
    if(oxygen <= 0){return -INF;}
    if(dp[y][x][oxygen] != -1){return dp[y][x][oxygen];}
    if(y == H){return oxygen;}
 
    int res = -INF;
    // x -> i -> j
    FOR(i, 1, W+1){
        FOR(j, 1, W+1){
            bool f = true;
            int first = x, last = i,
                step = x<i?+1:(x>i?-1:(i<j?+1:-1)), o = oxygen;
             
            while(first != last){
                first += step;
                o -= 1;
 
                if(o <= 0){f = false; break;}
 
                if(cell[y][first] > 0){
                    o = std::min(o+cell[y][first], M);
                }
            }
 
            if(!f){continue;}
 
            last = j;
            if((j <= i && i <= x) || (x <= i && i <= j)){
                while(first != last){
                    first += step;
                    o -= 1;
 
                    if(o <= 0){f = false; break;}
 
                    if(cell[y][first] > 0){
                        o = std::min(o+cell[y][first], M);
                    }
                }
            }else if((i <= j && j <= x) || (x <= j && j <= i)){
                step = -step;
                while(first != last){
                    first += step;
                    o -= 1;

                    if(o <= 0){f = false; break;}
                }
            }else{ // i - x - j, j - x - i
                last = x; step = -step;
                while(first != last){
                    first += step;
                    o -= 1;

                    if(o <= 0){f = false; break;}
                }

                last = j;
                while(first != last){
                    first += step;
                    o -= 1;
 
                    if(o <= 0){f = false; break;}
 
                    if(cell[y][first] > 0){
                        o = std::min(o+cell[y][first], M);
                    }
                }
            }
 
            if(!f){continue;}
 
            if(o <= 1){continue;}
 
            if(cell[y+1][j] > 0){
                res = std::max(res, rec(j, y+1, std::min(o-1+cell[y+1][j], M)));
            }else{
                res = std::max(res, rec(j, y+1, o-1));
            }
        }
    }
 
    return dp[y][x][oxygen] = res;
}

int main(){
    while(std::cin >> W >> H, W || H){
        std::cin >> F >> M >> O;

        FOR(i, 1, H+1){
            FOR(j, 1, W+1){
                std::cin >> cell[i][j];
            }
        }

        std::fill(&dp[0][0][0], &dp[0][0][0]+11*11*51, -1);

        bool f = false;
        FOR(i, 1, W+1){
            if(rec(i, 0, O) > 0){f = true;}
        }

        if(!f){puts("NA"); continue;}

        std::fill(&d[0][0][0], &d[0][0][0]+11*11*51, INF);

        std::priority_queue<State, std::vector<State>, std::greater<State>> q;
        FOR(i, 1, W+1){
            d[i][0][O] = 0;
            q.push(mp(d[i][0][O], mp(mp(i, 0), O)));
        }

        int mn = INF;
        while(!q.empty()){
            State s = q.top(); q.pop();
            int cost = s.first, x = s.second.first.first, y = s.second.first.second,
                o = s.second.second;

            if(o <= 0){continue;}
            if(cost > d[x][y][o]){continue;}
            if(y == H){mn = std::min(mn, cost); continue;}

            if(o == 1){continue;}
            REP(i, 3){
                int nx = x + dx[i], ny = y + dy[i];
                if(1 <= nx && nx <= W){
                    if(cell[ny][nx] < 0){ // cost
                        if(cost - cell[ny][nx] < d[nx][ny][o-1]){
                            d[nx][ny][o-1] = cost - cell[ny][nx];
                            q.push(mp(d[nx][ny][o-1], mp(mp(nx, ny), o-1)));
                        }
                    }else{ // oxygen
                        int new_o = std::min(o-1+cell[ny][nx], M);
                    
                        if(cost < d[nx][ny][new_o]){
                            d[nx][ny][new_o] = cost;
                            q.push(mp(d[nx][ny][new_o], mp(mp(nx, ny), new_o)));
                        }
                    }
                }
            }
        }

        if(mn > F){
            puts("NA");
        }else{
            printf("%d\n", mn);
        }
    }
}

Measured memory_bytes: 1240