#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <climits>
#include <queue>
#include <set>
#include <map>
#include <valarray>
#include <bitset>
#include <stack>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
typedef long long ll;
typedef pair<int,int> pii;
const int INF = 1<<29;
const double PI = acos(-1);
const double EPS = 1e-8;

struct P {
  int y,x,l,r,o,cost;
  P(int y,int x,int l, int r, int o, int cost) :
    y(y),x(x),l(l),r(r),o(o),cost(cost) {}
  bool operator<(const P &b) const {
    return cost > b.cost;
  }
};

int dist[11][10][10][10][51];

int ba[11][11];

int main() {
  int w,h;
  while(cin>>w>>h,w||h) {
    int f, m, o;
    cin >> f >> m >> o;
    memset(ba,0,sizeof(ba));
    REP(i,h) {
      REP(j,w) {
        cin >> ba[i][j];
      }
    }
    REP(i,h+1)REP(j,w)REP(l,w)REP(r,w)REP(k,m+1)dist[i][j][l][r][k]=INF;
    priority_queue<P> Q;
    if (o>=2) {
      REP(i,w) {
        int oo = o-1;
        int cc = 0;
        int t = ba[0][i];
        if (t > 0) oo = min(oo+t,m);
        else cc += -t;
        dist[0][i][i][i][oo] = cc;
        Q.push(P(0,i,i,i,oo,cc));
      }
    }
    int ans = -1;
    while(!Q.empty()) {
      P p = Q.top(); Q.pop();

      // printf("(%d,%d) [%d,%d], %d %d\n", p.y,p.x,p.l,p.r,p.o,p.cost);
      if (p.y == h-1) {
        ans = p.cost;
        break;
      }
      
      if (p.o == 1) continue;
      // left, right
      REP(i,2) {
        int xx = p.x + (i?-1:1);
        if (xx<0||xx>=w) continue;
        int l = p.l;
        int r = p.r;
        bool f = 0;
        if (xx < l) l--,f=1;
        if (xx > r) r++,f=1;
        int oo = p.o-1;
        int cc = p.cost;
        if (f) {                // dig
          int t = ba[p.y][xx];
          if (t > 0) {
            oo = min(oo+t,m);
          } else {
            cc += -t;
          }
        }
        if (dist[p.y][xx][l][r][oo] > cc) {
          dist[p.y][xx][l][r][oo] = cc;
          Q.push(P(p.y,xx,l,r,oo,cc));
        }
      }
      // down
      int yy = p.y+1;
      int oo = p.o-1;
      int cc = p.cost;
      int t = ba[yy][p.x];
      if (t > 0) oo = min(oo+t,m);
      else cc += -t;
      if (dist[yy][p.x][p.x][p.x][oo] > cc) {
        dist[yy][p.x][p.x][p.x][oo] = cc;
        Q.push(P(yy,p.x,p.x,p.x,oo,cc));
      }
    }
    if (ans == -1 || ans>f) puts("NA");
    else cout << ans << endl;
  }
}