#include <bits/stdc++.h>
using namespace std;
const int maxn = 50 + 5;
const long long inf = 1e9 + 7;
inline int read() {
  int X = 0, w = 0;
  char ch = 0;
  while (!isdigit(ch)) {
    w |= ch == '-';
    ch = getchar();
  }
  while (isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();
  return w ? -X : X;
}
struct edge {
  int from, to, cap, flow, cost;
  edge(int a, int b, int c, int d, int e) {
    from = a, to = b, cap = c, flow = d, cost = e;
  }
};
long long n, m;
int startPoint, endPoint;
struct MCMF {
  int n;
  vector<edge> e;
  vector<int> g[maxn];
  int inq[maxn];
  int d[maxn];
  int p[maxn];
  int a[maxn];
  void Init(int n) {
    this->n = n;
    for (int i = 0; i <= n; i++) g[i].clear();
    e.clear();
  }
  void add(int from, int to, int cap, int cost) {
    e.push_back(edge(from, to, cap, 0, cost));
    e.push_back(edge(to, from, 0, 0, -cost));
    int m = e.size();
    g[from].push_back(m - 2);
    g[to].push_back(m - 1);
  }
  bool bellman(int s, int t, int& flow, int& cost) {
    for (int i = 0; i <= t; i++) d[i] = inf, inq[i] = 0;
    d[s] = 0;
    inq[s] = 1;
    p[s] = 0;
    a[s] = inf;
    queue<int> Q;
    Q.push(s);
    while (!Q.empty()) {
      int u = Q.front();
      Q.pop();
      inq[u] = 0;
      for (int i = 0; i < g[u].size(); i++) {
        edge& ee = e[g[u][i]];
        if (ee.cap > ee.flow && d[ee.to] > d[u] + ee.cost &&
            d[u] + ee.cost <= m) {
          d[ee.to] = d[u] + ee.cost;
          p[ee.to] = g[u][i];
          a[ee.to] = min(a[u], ee.cap - ee.flow);
          if (!inq[ee.to]) {
            Q.push(ee.to);
            inq[ee.to] = 1;
          }
        }
      }
    }
    if (d[t] == inf) return false;
    if (d[t] * a[t] > m - cost) {
      a[t] = (m - cost) / d[t];
      flow += a[t];
      cost += d[t] * a[t];
    } else {
      flow += a[t];
      cost += d[t] * a[t];
    }
    if (a[t] == 0) return false;
    int u = t;
    while (u != s) {
      e[p[u]].flow += a[t];
      e[p[u] ^ 1].flow -= a[t];
      u = e[p[u]].from;
    }
    return true;
  }
  int minCost(int s, int t) {
    int flow = 0, cost = 0;
    while (bellman(s, t, flow, cost)) {
      if (m != 0 && cost >= m) break;
    }
    return flow;
  }
} solve;
int main() {
  cin >> n >> m;
  startPoint = 1, endPoint = n;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      int x;
      scanf("%d", &x);
      if (i == j) continue;
      if (x > 0) {
        solve.add(i, j, x, 0);
        solve.add(i, j, m, 1);
      }
    }
  }
  printf("%d\n", solve.minCost(startPoint, endPoint));
  return 0;
}
