#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) { return a % b == 0 ? b : gcd(b, a % b); }
const int INF = 1 << 30;
const double eps = 1e-8;
const int row = 3000;
const int cow = 1000;
const int MAXN = cow * cow;
int n, m, cnt, ans, tem;
int f[cow], dp[cow], pre[cow], sta[cow];
struct edge {
  int to, next, f, v;
} e[100000];
void add(int x, int y, int ff, int v) {
  e[cnt].to = y;
  e[cnt].next = f[x];
  e[cnt].v = v;
  e[cnt].f = ff;
  f[x] = cnt++;
  e[cnt].to = x;
  e[cnt].next = f[y];
  e[cnt].v = -v;
  e[cnt].f = 0;
  f[y] = cnt++;
}
bool BFS() {
  int i, j;
  for (i = 0; i < 55; i++) dp[i] = INF;
  dp[1] = 0;
  queue<int> que;
  que.push(1);
  while (!que.empty()) {
    int x = que.front();
    que.pop();
    for (i = f[x]; i != -1; i = e[i].next) {
      if (e[i].f && dp[x] + e[i].v < dp[e[i].to]) {
        dp[e[i].to] = dp[x] + e[i].v;
        pre[e[i].to] = x;
        sta[e[i].to] = i;
        que.push(e[i].to);
      }
    }
  }
  if (dp[n] == INF) return false;
  int a = INF;
  for (i = n; i != 1; i = pre[i]) {
    a = min(a, e[sta[i]].f);
  }
  if (dp[n] != 0) {
    int t = m / dp[n];
    if (t < a) {
      ans += t;
      return false;
    }
  }
  return true;
}
int solve() {
  int i, j;
  while (BFS()) {
    int a = INF;
    for (i = n; i != 1; i = pre[i]) {
      a = min(a, e[sta[i]].f);
    }
    if (dp[n] != 0) {
      int t = m / dp[n];
      a = min(a, t);
    }
    for (i = n; i != 1; i = pre[i]) {
      e[sta[i]].f -= a;
      e[sta[i] ^ 1].f += a;
    }
    m -= (dp[n] * a);
    ans += a;
  }
  return ans;
}
int main() {
  int i, j, t;
  cnt = 0, ans = 0;
  scanf("%d%d", &n, &m);
  memset(f, -1, sizeof(f));
  for (i = 1; i <= n; i++) {
    for (j = 1; j <= n; j++) {
      int a;
      scanf("%d", &a);
      if (a) {
        add(i, j, a, 0);
        add(i, j, m, 1);
      }
    }
  }
  cout << solve() << endl;
  return 0;
}
