#include <bits/stdc++.h>
using namespace std;
long long MOD = 1000000007;
long long n, adjMat[50][50];
long long augMat[50][50][3];
void printAugMat() {
  for (long long i = 0; i < (n); ++i) {
    for (long long j = 0; j < (n); ++j) {
      printf("(%lld %lld %lld) ", augMat[i][j][0], augMat[i][j][1],
             augMat[i][j][2]);
    }
    putchar(10);
  }
}
std::pair<int, int> augmentPath(long long src, long long dest) {
  bool vis[50];
  long long cost[50];
  long long par[50][2];
  for (long long i = 0; i < (n); ++i) par[i][0] = -1;
  priority_queue<std::pair<int, int>, vector<std::pair<int, int> >,
                 greater<std::pair<int, int> > >
      pq;
  for (long long i = 0; i < (n); ++i) vis[i] = 0;
  for (long long i = 0; i < (n); ++i) cost[i] = MOD;
  pq.push({0, src});
  cost[src] = 0;
  while (!pq.empty()) {
    std::pair<int, int> nd = pq.top();
    pq.pop();
    if (vis[nd.second]) continue;
    vis[nd.second] = true;
    long long v = nd.second;
    if (v == dest) break;
    for (long long c = 0; c < n; ++c) {
      if (vis[c]) continue;
      for (long long i = 0; i < 3; ++i) {
        if (augMat[v][c][i] > 0) {
          long long cst = 1 - i;
          if (cost[c] > cost[v] + cst) {
            cost[c] = cost[v] + cst;
            pq.push({cost[c], c});
            par[c][0] = v;
            par[c][1] = i;
          }
        }
      }
    }
  }
  while (!pq.empty()) pq.pop();
  long long nw = dest, cap = 2 * MOD, cst = 0;
  while (par[nw][0] != -1) {
    long long p = par[nw][0];
    long long w = par[nw][1];
    cap = min(cap, augMat[p][nw][w]);
    cst += 1 - w;
    nw = p;
  }
  if (cap == 2 * MOD) return {0, cst};
  nw = dest;
  while (par[nw][0] != -1) {
    long long p = par[nw][0];
    long long w = par[nw][1];
    augMat[p][nw][w] -= cap;
    augMat[nw][p][2 - w] += cap;
    nw = p;
  }
  return {cap, cst};
}
long long minCostmaxFlow(long long src, long long dest, long long Flow) {
  for (long long i = 0; i < (n); ++i)
    for (long long j = 0; j < (n); ++j) {
      augMat[i][j][1] = adjMat[i][j];
      augMat[i][j][0] = (adjMat[i][j] == 0 ? 0 : MOD);
      augMat[i][j][2] = 0;
    }
  long long minCost = 0;
  while (Flow > 0) {
    std::pair<int, int> pp = augmentPath(src, dest);
    if (pp.first == 0) break;
    if (pp.first > Flow) {
      minCost += pp.second * Flow;
      Flow -= Flow;
    } else {
      minCost += pp.second * pp.first;
      Flow -= pp.first;
    }
  }
  if (Flow == 0)
    return minCost;
  else
    return MOD;
}
int main() {
  long long K;
  scanf("%lld %lld", &n, &K);
  for (long long i = 0; i < (n); ++i)
    for (long long j = 0; j < (n); ++j) cin >> adjMat[i][j];
  long long l = 0, r = MOD, m;
  while (r - l > 1) {
    m = (l + r) / 2;
    long long cst = minCostmaxFlow(0, n - 1, m);
    if (cst <= K)
      l = m;
    else
      r = m;
  }
  if (minCostmaxFlow(0, n - 1, r) <= K)
    cout << r << endl;
  else
    cout << l << endl;
  return 0;
}
