#include <bits/stdc++.h>
struct graph {
  struct edge {
    int to, val, cst, opp;
  };
  std::vector<edge> a[55];
  int n, s, t, dis[55], vis[55], inq[55], nxt[55], can[55];
  void add(int x, int y, int v, int w) {
    int p = a[x].size(), q = a[y].size();
    a[x].push_back(edge{y, v, w, q});
    a[y].push_back(edge{x, 0, -w, p});
  }
  int spfa(int s, int t) {
    std::queue<int> q;
    for (int i = 1; i <= n; i++)
      dis[i] = 1000000000, vis[i] = 0, inq[i] = 0, nxt[i] = 1, can[i] = 0;
    q.push(s);
    dis[s] = 0;
    inq[s] = 1;
    while (!q.empty()) {
      int v = q.front();
      q.pop();
      inq[v] = 0;
      for (int i = 0; i < a[v].size(); i++) {
        int u = a[v][i].to;
        if (dis[v] + a[v][i].cst < dis[u] && a[v][i].val) {
          dis[u] = dis[v] + a[v][i].cst;
          if (!inq[u]) q.push(u), inq[u] = 1;
        }
      }
    }
    return dis[t];
  }
  int dfs(int v, int t, int now) {
    if (vis[v]) return 0;
    vis[v] = 1;
    if (!nxt[v]) now = 0;
    if (v == t || !now) return now;
    int cnt = 0;
    for (int i = can[v]; i < a[v].size(); i++) {
      ++can[v];
      int u = a[v][i].to;
      if (!a[v][i].val || dis[v] + a[v][i].cst != dis[u]) continue;
      int k = dfs(u, t, std::min(now, a[v][i].val));
      if (!k) continue;
      cnt = cnt + k;
      now = now - k;
      a[v][i].val = a[v][i].val - k;
      a[u][a[v][i].opp].val = a[u][a[v][i].opp].val + k;
      if (!now) {
        --can[v];
        break;
      }
    }
    if (!cnt) nxt[v] = 0;
    return cnt;
  }
  std::pair<int, int> mcmf(int ss, int tt, int lim) {
    int ans = 0;
    s = ss, t = tt;
    int x = lim;
    while (1) {
      std::pair<int, int> cnt;
      cnt.second = spfa(s, t);
      if (cnt.second == 1000000000 || x < cnt.second) break;
      cnt.first = dfs(s, t, cnt.second ? x / cnt.second : 1000000000);
      if (cnt.first * cnt.second <= x)
        x = x - cnt.first * cnt.second, ans = ans + cnt.first;
      else {
        ans = ans + x / cnt.second;
        x = x - x / cnt.second * cnt.second;
        return std::make_pair(ans, lim - x);
      }
    }
    return std::make_pair(ans, lim - x);
  }
};
graph g;
int n, k;
int main() {
  scanf("%d%d", &n, &k);
  g.n = n;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
      int x;
      scanf("%d", &x);
      if (!x) continue;
      g.add(i, j, x, 0);
      g.add(i, j, k, 1);
    }
  printf("%d\n", g.mcmf(1, n, k).first);
  return 0;
}
