#include <bits/stdc++.h>
using namespace std;
const long long wEPS = 0;
const long long wINF = 1LL << 55;
const long long cEPS = 0;
const long long cINF = 1LL << 55;
struct MCF {
  int n, m, ptr[60], next[10000], zu[10000];
  long long capa[10000], tof;
  long long cost[10000], toc, d[60], pot[60];
  int vis[60], pree[60];
  long long CL;
  MCF(int _n, long long costlimit) {
    n = _n;
    m = 0;
    memset(ptr, ~0, n << 2);
    CL = costlimit;
  }
  void ae(int u, int v, long long w, long long c) {
    next[m] = ptr[u];
    ptr[u] = m;
    zu[m] = v;
    capa[m] = w;
    cost[m] = +c;
    ++m;
    next[m] = ptr[v];
    ptr[v] = m;
    zu[m] = u;
    capa[m] = 0;
    cost[m] = -c;
    ++m;
  }
  bool run(int src, int ink, long long flo = wINF) {
    long long f;
    long long c, cc;
    int i, u, v;
    memset(pot, 0, n * sizeof(long long));
    for (bool cont = 1; cont;) {
      cont = 0;
      for (u = 0; u < n; ++u)
        for (i = ptr[u]; ~i; i = next[i])
          if (capa[i] > wEPS) {
            if (pot[zu[i]] > pot[u] + cost[i] + cEPS) {
              pot[zu[i]] = pot[u] + cost[i];
              cont = 1;
            }
          }
    }
    for (toc = 0, tof = 0; tof + wEPS < flo;) {
      priority_queue<pair<long long, int>, vector<pair<long long, int> >,
                     greater<pair<long long, int> > >
          q;
      for (u = 0; u < n; ++u) {
        d[u] = cINF;
        vis[u] = 0;
      }
      for (q.push(make_pair(d[src] = 0, src)); !q.empty();) {
        c = q.top().first;
        u = q.top().second;
        q.pop();
        if (vis[u]++) continue;
        for (i = ptr[u]; ~i; i = next[i])
          if (capa[i] > wEPS) {
            cc = c + cost[i] + pot[u] - pot[v = zu[i]];
            if (cc + toc > CL) continue;
            if (d[v] > cc) {
              q.push(make_pair(d[v] = cc, v));
              pree[v] = i;
            }
          }
      }
      if (!vis[ink]) return 0;
      f = flo - tof;
      for (v = ink; v != src; v = zu[i ^ 1]) {
        i = pree[v];
        f = min(f, capa[i]);
      }
      if ((d[ink] - pot[src] + pot[ink]))
        f = min((d[ink] - pot[src] + pot[ink]) * f, CL - toc) /
            (d[ink] - pot[src] + pot[ink]);
      if (!f) return 0;
      for (v = ink; v != src; v = zu[i ^ 1]) {
        i = pree[v];
        capa[i] -= f;
        capa[i ^ 1] += f;
      }
      tof += f;
      toc += f * (d[ink] - pot[src] + pot[ink]);
      for (u = 0; u < n; ++u) pot[u] += d[u];
    }
    return 1;
  }
};
int main() {
  int n, k;
  cin >> n >> k;
  MCF FF(n, k);
  for (__typeof(n) i = 0; i < (n); i++) {
    for (__typeof(n) j = 0; j < (n); j++) {
      int temp;
      scanf("%d", &temp);
      if (i != j && temp) {
        FF.ae(i, j, temp, 0);
        FF.ae(i, j, 1LL << 55, 1);
      }
    }
  }
  FF.run(0, n - 1);
  cout << FF.tof << endl;
  return 0;
}
