#include <bits/stdc++.h>
using namespace std;
void RI() {}
template <typename... T>
void RI(int& head, T&... tail) {
  scanf("%d", &head);
  RI(tail...);
}
mt19937 rng(0x5EED);
int randint(int lb, int ub) {
  return uniform_int_distribution<int>(lb, ub)(rng);
}
const int INF = 1029384756;
struct Edge {
  int v, f, c, re;
};
int N, K;
int dis[54], pre[54], preL[54];
int fr, bk, que[54], inq[54];
vector<Edge> E[54];
void add_edge(int u, int v, int f, int c) {
  E[u].push_back({v, f, c, (int)E[v].size()});
  E[v].push_back({u, 0, -c, (int)E[u].size() - 1});
}
int main(int argc, char** argv) {
  cin >> N >> K;
  for (int i = 0; i < N; i++) {
    for (int j = 0, v; j < N; j++) {
      cin >> v;
      if (v) {
        add_edge(i, j, v, 0);
        add_edge(i, j, INF, 1);
      }
    }
  }
  int flow = 0;
  int cost = 0;
  int second = 0;
  int T = N - 1;
  while (true) {
    for (int i = 0; i < N; i++) {
      dis[i] = INF;
      pre[i] = preL[i] = -1;
      inq[i] = 0;
    }
    fr = bk = 0;
    que[bk++] = second;
    inq[second] = 1;
    dis[second] = 0;
    while (fr != bk) {
      int u = que[fr++];
      if (fr >= 54) fr -= 54;
      for (int i = 0; i < (int)E[u].size(); i++) {
        if (E[u][i].f <= 0) continue;
        int v = E[u][i].v;
        if (dis[v] > dis[u] + E[u][i].c) {
          dis[v] = dis[u] + E[u][i].c;
          pre[v] = u;
          preL[v] = i;
          if (!inq[v]) {
            inq[v] = 1;
            que[bk++] = v;
            if (bk >= 54) bk -= 54;
          }
        }
      }
      inq[u] = 0;
    }
    if (dis[T] == INF) break;
    int f = INF;
    int v = T;
    while (v != second) {
      int u = pre[v];
      f = min(f, E[u][preL[v]].f);
      v = u;
    }
    if (1ll * dis[T] * f + cost <= K) {
      flow += f;
      cost += dis[T] * f;
    } else {
      int bye = 0;
      for (int i = 0; i < f; i++) {
        if (dis[T] + cost <= K) {
          cost += dis[T];
          flow++;
        } else {
          bye = 1;
        }
      }
      if (bye) break;
    }
    v = T;
    while (v != second) {
      int u = pre[v];
      E[u][preL[v]].f -= f;
      int rl = E[u][preL[v]].re;
      E[v][rl].f += f;
      v = u;
    }
  }
  cout << flow << endl;
  return 0;
}
