#include <bits/stdc++.h>
using namespace std;
const int N = 400;
const int M = 10000;
const int INF = 100000000;
struct edge {
  int d, k, data, cost, next, ref;
} e[M];
int first[N], d[N], b[N * 10], pre[N], mi[N];
bool bi[N], flag[N];
int p1, p2, p3, ans, n, m, S, T, nn, maxflow;
void addedge(int p, int q, int k, int c) {
  e[++nn].k = q;
  e[nn].d = p;
  e[nn].data = k;
  e[nn].cost = c;
  e[nn].ref = nn + 1;
  e[nn].next = first[p];
  first[p] = nn;
  e[++nn].k = p;
  e[nn].d = q;
  e[nn].data = 0;
  e[nn].cost = -c;
  e[nn].ref = nn - 1;
  e[nn].next = first[q];
  first[q] = nn;
}
void relax(int p, int q, int k, int num) {
  if (d[q] > d[p] + k) {
    d[q] = d[p] + k;
    pre[q] = num;
    if (bi[q]) {
      bi[q] = false;
      p2++;
      if (p2 == N * 10) p2 = 1;
      b[p2] = q;
      ++p3;
    }
  }
}
int spfa() {
  memset(bi, true, sizeof(bi));
  memset(d, 100, sizeof(d));
  d[S] = 0;
  bi[S] = false;
  b[1] = S;
  p1 = 1;
  p2 = 1;
  p3 = 1;
  while (p3) {
    int p = b[p1];
    for (int i = first[p]; i; i = e[i].next)
      if (e[i].data > 0) relax(p, e[i].k, e[i].cost, i);
    bi[p] = true;
    p3--;
    p1++;
    if (p1 == N * 10) p1 = 1;
  }
  if (d[T] > INF) return 1;
  int j = T, flow = INF;
  while (j != S) {
    flow = min(flow, e[pre[j]].data);
    j = e[pre[j]].d;
  }
  return flow;
}
void update(int flow) {
  maxflow += flow;
  int j = T;
  while (j != S) {
    ans += e[pre[j]].cost * flow;
    e[pre[j]].data -= flow;
    e[e[pre[j]].ref].data += flow;
    j = e[pre[j]].d;
  }
}
int k;
int main() {
  while (scanf("%d%d", &n, &k) == 2) {
    nn = 0;
    memset(first, 0, sizeof(first));
    S = 1;
    T = n;
    int p1;
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= n; ++j) {
        scanf("%d", &p1);
        addedge(i, j, p1, 0);
        if (p1) addedge(i, j, 1000, 1);
      }
    ans = maxflow = 0;
    int now = 0;
    while (1) {
      int t = spfa(), q = d[T];
      if (now + q > k) break;
      if (q == 0)
        update(t);
      else {
        int trans = min(t, (k - now) / q);
        now += q * trans;
        update(trans);
      }
    }
    printf("%d\n", maxflow);
  }
  return 0;
}
