#include <bits/stdc++.h>
using namespace std;
const double eps = 0.000000000000001;
const int N = 60;
int n, k, take = 0;
int cap[N][N][4], dis[N];
int wt[N][N][4];
pair<int, int> par[N];
int vis[N];
int inf = (1 << 29);
int pbfs(int s, int d) {
  int i, j;
  priority_queue<pair<int, int>, vector<pair<int, int> >,
                 greater<pair<int, int> > >
      pq;
  for (i = 0; i <= n; i++) {
    vis[i] = 0;
    dis[i] = inf;
  }
  pq.push(make_pair(0, s));
  par[s] = par[d] = make_pair(-1, 0);
  dis[s] = 0;
  while (!pq.empty()) {
    pair<int, int> cur = pq.top();
    pq.pop();
    int c = cur.second;
    if (vis[c]) continue;
    vis[c] = 1;
    for (i = 1; i <= n; i++) {
      for (j = 0; j < 4; j++) {
        if (vis[i] == 0 && cap[c][i][j] > 0 && dis[i] > dis[c] + wt[c][i][j]) {
          dis[i] = dis[c] + wt[c][i][j];
          par[i] = make_pair(c, j);
          pq.push(make_pair(dis[i], i));
        }
      }
    }
  }
  if (par[d].first == -1) {
    return 0;
  }
  int x = d, mn = inf;
  while (par[x].first != -1) {
    int p = par[x].first;
    mn = min(mn, cap[p][x][par[x].second]);
    x = p;
  }
  if (dis[d] > 0) {
    int left = k - take;
    if (left / dis[d] > 0) {
      mn = min(mn, left / dis[d]);
      take += (mn)*dis[d];
    } else
      return 0;
  }
  x = d;
  while (par[x].first != -1) {
    int p = par[x].first;
    cap[p][x][par[x].second] -= mn;
    cap[x][p][par[x].second + ((par[x].second & 1) ? -1 : 1)] += mn;
    x = p;
  }
  assert(mn < inf);
  return mn;
}
long long getmaxflow(int x, int y) {
  long long ret = 0, dis = 0;
  while ((dis = pbfs(x, y)) > 0) {
    ret += dis;
  }
  return ret;
}
int main() {
  scanf("%d%d", &n, &k);
  int i, j, d;
  for (i = 1; i <= n; i++) {
    for (j = 1; j <= n; j++) {
      scanf("%d", &d);
      cap[i][j][0] = d;
      if (d > 0) cap[i][j][2] = inf;
      wt[i][j][2] = 1;
      wt[j][i][3] = -1;
    }
  }
  long long ans = getmaxflow(1, n);
  printf("%lld\n", ans);
  return 0;
}
