#include <bits/stdc++.h>
using namespace std;
const int inf = 1000000000;
struct edge {
  int to, next, f, fm, v;
} e[500010];
int num, n, m, ans, c, h, t, flow;
int dis[5005], fw[5005], q[5005], head[5005], p[5005];
bool vis[5005];
void addedge(int x, int y, int flow, int cost) {
  num++;
  e[num].to = y;
  e[num].fm = x;
  e[num].next = head[x];
  e[num].f = flow;
  e[num].v = cost;
  head[x] = num;
}
bool mcmf() {
  int k, u;
  for (int i = 1; i <= n; i++) {
    dis[i] = inf;
    vis[i] = false;
    fw[i] = 0;
    p[i] = -1;
  }
  h = 0;
  t = 1;
  q[1] = 1;
  dis[1] = 0;
  fw[1] = inf;
  while (h < t) {
    h++;
    if (h > 5000) h = 1;
    k = q[h];
    vis[k] = false;
    for (int j = head[k]; j; j = e[j].next) {
      u = e[j].to;
      if (dis[k] + e[j].v < dis[u] && e[j].f) {
        dis[u] = dis[k] + e[j].v;
        p[u] = j;
        fw[u] = min(fw[k], e[j].f);
        if (!vis[u]) {
          vis[u] = true;
          t++;
          if (t > 5000) t = 1;
          q[t] = u;
        }
      }
    }
  }
  if (dis[n] >= inf) return false;
  if (c + dis[n] * fw[n] > m) {
    ans += (m - c) / dis[n];
    return false;
  }
  ans += fw[n];
  c += fw[n] * dis[n];
  int fr = p[n];
  while (fr != -1) {
    e[fr].f -= fw[n];
    e[fr ^ 1].f += fw[n];
    fr = p[e[fr].fm];
  }
  return true;
}
void solve() {
  while (mcmf())
    ;
}
int main() {
  scanf("%d%d", &n, &m);
  num = 1;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
      scanf("%d", &flow);
      if (!flow) continue;
      addedge(i, j, flow, 0);
      addedge(j, i, 0, 0);
      addedge(i, j, m, 1);
      addedge(j, i, 0, -1);
    }
  solve();
  printf("%d\n", ans);
  return 0;
}
