#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <tr1/unordered_map>

using namespace std;
using namespace tr1;

struct State {
    char x, y, oxygen, left, right;

    State(int x, int y, int o, int l, int r) : x(x), y(y), oxygen(o), left(l), right(r) {}

    bool operator ==(const State &other) const {
        return x == other.x
            && y == other.y
            && oxygen == other.oxygen
            && left == other.left
            && right == other.right;
    }
    struct Hasher {
        size_t operator ()(const State &state) const {
            return (int)state.right + (int)state.left*10 + (int)state.oxygen*10*10 + (int)state.y*10*10*51 + (int)state.x*10*10*51*11;
        }
    };
};

struct Tag {
    State state;
    int cost;

    Tag(const State &s, int c) : state(s), cost(c) {}

    bool operator <(const Tag &other) const {
        return cost > other.cost; // reverse order
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    while(true) {
        int W, H;
        cin >> W >> H;
        if(!W && !H) break;
        int F, M, O;
        cin >> F >> M >> O;
        vector<vector<int> > field(H+1, vector<int>(W)); 
        // テヲツ慊?・ツ按敕」ツ?ョティツ。ツ古」ツ?ッテゥツ?クテァツエツ?テ」ツ?ョテ」ツつサテ」ツδォテ」ツ?ァテ・ツ淞凝」ツ?セテ」ツ?」テ」ツ?ヲテ」ツ??」ツつ凝」ツ?ィテ」ツ?凖」ツつ?テァツ閉ェテ・ツ?オ)
        for(int x = 0; x < W; ++x) {
            field[0][x] = 1;
        }
        for(int y = 1; y <= H; ++y) {
            for(int x = 0; x < W; ++x) {
                cin >> field[y][x];
            }
        }

        int ans = F+1;
        priority_queue<Tag> q;
        unordered_map<State,int,State::Hasher> memo;
        // テ・ツ按敕ヲツ慊淌ァツ環カテヲツ??
        q.push(Tag(State(0, 0, O, 0, 0), 0));
        memo[q.top().state] = q.top().cost;
        while(!q.empty()) {
            const Tag t = q.top();
            q.pop();
            if(memo.count(t.state) && memo[t.state] < t.cost) continue;
            memo[t.state] = t.cost;

            if(t.state.y == H) {
                ans = t.cost;
                break;
            }

            const static int dx[] = {1, -1, 0};
            const static int dy[] = {0, 0, 1};
            for(int pat = 0; pat < 3; ++pat) {
                bool is_down = (pat == 2);
                const int nx = t.state.x + dx[pat];
                const int ny = t.state.y + dy[pat];
                int no = t.state.oxygen - 1;
                int nc = t.cost;
                if(no <= 0) continue; // テゥツ?クテァツエツ?」ツ?古」ツ?ェテ」ツ?湘」ツ?ェテ」ツ?」テ」ツ?淌」ツつ嘉・ツ債ウテヲツュツサ
                if(nx < 0 || W <= nx || ny >= H+1) continue;
                // テ」ツ?セテ」ツ??ヲツ篠佚」ツ?」テ」ツ?ヲテ」ツ?ェテ」ツ??・ツ?エテヲツ可?」ツ?ョテ」ツ?ソテ」ツつ、テ」ツδ凖」ツδウテ」ツδ暗ァツ卍コテァツ板?
                if(is_down || !(t.state.left <= nx && nx <= t.state.right)) {
                    const int cell = field[ny][nx];
                    if(cell > 0) {
                        no = min(no+cell, M);
                    } else {
                        nc -= cell;
                    }
                }
                const int nl = is_down ? nx : min((int)t.state.left, nx);
                const int nr = is_down ? nx : max((int)t.state.right, nx);
                const State next_state(nx, ny, no, nl, nr);
                if(memo.count(next_state) && memo[next_state] <= nc) continue;
                memo[next_state] = nc;
                q.push(Tag(next_state, nc));
            }
        }
        if(ans > F) cout << "NA" << endl;
        else cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 1732