#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
using namespace std;
const int maxn = 404;
int n, m, k;
int s[103], t[103];
int c[103][103], d[103][103], e[103][103], f[103][103];
struct Edge {
  int u, v, c, w, next;
  Edge(int u, int v, int c, int w, int next)
      : u(u), v(v), c(c), w(w), next(next) {}
  Edge() {}
} edge[100005];
int head[maxn], E;
void init() {
  memset(head, -1, sizeof(head));
  E = 0;
}
void add(int s, int t, int c, int w) {
  edge[E] = Edge(s, t, c, w, head[s]);
  head[s] = E++;
  edge[E] = Edge(t, s, 0, -w, head[t]);
  head[t] = E++;
}
int S, T;
int pre[maxn], dis[maxn];
bool vis[maxn];
bool spfa(int s, int t, int n) {
  int i, u, v;
  for (i = 0; i <= n; i++) dis[i] = inf, pre[i] = -1, vis[i] = false;
  queue<int> q;
  vis[s] = true;
  dis[s] = 0;
  q.push(s);
  while (!q.empty()) {
    u = q.front();
    q.pop();
    vis[u] = false;
    for (i = head[u]; ~i; i = edge[i].next) {
      v = edge[i].v;
      if (edge[i].c && dis[v] > dis[u] + edge[i].w) {
        dis[v] = dis[u] + edge[i].w;
        pre[v] = i;
        if (!vis[v]) {
          vis[v] = true;
          q.push(v);
        }
      }
    }
  }
  if (dis[t] == inf) return 0;
  return 1;
}
int ans;
pair<int, int> mcmf(int s, int t, int n) {
  int aug, minc = 0, i, maxf = 0;
  while (spfa(s, t, n)) {
    aug = inf + 1;
    for (i = pre[t]; ~i; i = pre[edge[i].u]) aug = min(aug, edge[i].c);
    for (i = pre[t]; ~i; i = pre[edge[i].u]) {
      edge[i].c -= aug;
      edge[i ^ 1].c += aug;
    }
    maxf += aug;
    minc += dis[t] * aug;
  }
  return make_pair(maxf, minc);
}
int Map[55][55];
void build(int m) {
  int i, j;
  init();
  for (i = 0; i < n; i++)
    for (j = 0; j < n; j++) {
      if (Map[i][j]) {
        add(i, j, Map[i][j], 0);
        add(i, j, k, 1);
      }
    }
  add(n, 0, m, 0);
}
int main() {
  int i, j;
  scanf("%d%d", &n, &k);
  for (i = 0; i < n; i++)
    for (j = 0; j < n; j++) scanf("%d", &Map[i][j]);
  int l = 0, r = 1e9;
  while (l <= r) {
    int m = (l + r) >> 1;
    build(m);
    pair<int, int> t = mcmf(n, n - 1, n + 1);
    if (t.first == m && t.second <= k) {
      l = m + 1;
      ans = m;
    } else
      r = m - 1;
  }
  printf("%d\n", ans);
  return 0;
}
