#include <bits/stdc++.h>
using namespace std;
const int maxn = 140;
const int mask = 127;
const int INF = 0x7f7f7f7f;
const int mod = 10007;
const unsigned long long X = 123;
template <typename T>
T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}
struct node {
  int v, next, w, c;
} edge[111111], redge[111111];
int e, head[maxn];
int c[55][55];
void add_edge(int u, int v, int c, int cost) {
  edge[e].v = v;
  edge[e].next = head[u];
  edge[e].c = c;
  edge[e].w = cost;
  head[u] = e++;
}
int q[maxn];
int cur[maxn];
int pre[maxn];
int dis[maxn];
bool inq[maxn];
int spfa(int s, int t, int n) {
  int front, rear, i, u, v;
  front = rear = 0;
  memset(dis, 0x7f, sizeof(dis));
  memset(inq, false, sizeof(inq));
  dis[s] = 0;
  q[rear++] = s;
  while (front ^ rear) {
    u = q[front++];
    inq[u] = false;
    front &= mask;
    for (i = head[u]; ~i; i = edge[i].next) {
      v = edge[i].v;
      if (dis[v] > dis[u] + edge[i].w && edge[i].c > 0) {
        dis[v] = dis[u] + edge[i].w;
        cur[v] = i;
        pre[v] = u;
        if (!inq[v]) {
          q[rear++] = v;
          rear &= mask;
          inq[v] = false;
        }
      }
    }
  }
  return dis[t];
}
long long MCMF(int s, int t, int n) {
  int flow = 0, aug = 0, u, v;
  long long res = 0;
  while (true) {
    int cost = spfa(s, t, n);
    if (cost == INF) break;
    aug = INF;
    u = v = t;
    for (u = t; u ^ s; v = u, u = pre[u]) {
      aug = min(aug, edge[cur[u]].c);
    }
    flow += aug;
    res = res + 1LL * aug * cost;
    v = u = t;
    for (u = t; u ^ s; v = u, u = pre[u]) {
      edge[cur[u]].c -= aug;
      edge[cur[u] ^ 1].c += aug;
    }
  }
  return res;
}
int main() {
  ios::sync_with_stdio(false);
  int n, k, i, j;
  e = 0;
  memset(head, -1, sizeof(head));
  scanf("%d%d", &n, &k);
  add_edge(0, 1, 10000, 0);
  add_edge(1, 0, 0, 0);
  for (i = 1; i <= n; ++i) {
    for (j = 1; j <= n; ++j) {
      scanf("%d", c[i] + j);
      if (c[i][j]) {
        add_edge(i, j, c[i][j], 0);
        add_edge(j, i, 0, 0);
        add_edge(i, j, INF, 1);
        add_edge(j, i, 0, -1);
      }
    }
  }
  int p = spfa(1, n, n);
  if (p == INF) {
    puts("0");
    return 0;
  }
  copy(edge, edge + e, redge);
  int l = 0, ans = 0, r = (int)(1e9), mid;
  while (l <= r) {
    mid = (l + r) >> 1;
    copy(redge, redge + e, edge);
    edge[0].c = mid;
    long long tv = MCMF(0, n, n);
    if (tv <= k) {
      l = mid + 1;
      ans = mid;
    } else {
      r = mid - 1;
    }
  }
  printf("%d\n", ans);
  return 0;
}
