#include <bits/stdc++.h>
using namespace std;
const int MAXN = 51;
const int INF = 5e7 + 1;
struct Edge {
  int to, cap, cost;
  Edge(int to, int cap, int cost) : to(to), cap(cap), cost(cost) {}
};
vector<int> g[MAXN];
vector<Edge> e;
int d[MAXN];
int q[MAXN], qh, qt;
bool queued[MAXN];
int p[MAXN];
int n, k;
int a[51][51];
void addEdge(int a, int b, int cap, int cost) {
  g[a].push_back(e.size());
  e.push_back(Edge(b, cap, cost));
  g[b].push_back(e.size());
  e.push_back(Edge(a, 0, -cost));
}
bool spfa() {
  for (int i = 1; i <= n; ++i) {
    d[i] = INF;
    queued[i] = false;
  }
  d[1] = 0;
  qt = qh = 0;
  q[qt++] = 1;
  queued[1] = true;
  while (qh != qt) {
    int v = q[qh++];
    queued[v] = false;
    if (qh == MAXN) qh = 0;
    for (int i = 0, id; i < g[v].size(); ++i) {
      id = g[v][i];
      if (e[id].cap > 0 && d[e[id].to] > d[v] + e[id].cost) {
        d[e[id].to] = d[v] + e[id].cost;
        p[e[id].to] = id;
        if (!queued[e[id].to]) {
          queued[e[id].to] = true;
          q[qt++] = e[id].to;
          if (qt == MAXN) qt = 0;
        }
      }
    }
  }
  return d[n] != INF;
}
int flow() {
  int res = 0;
  while (k >= 0 && spfa()) {
    int Flow = INF;
    for (int y = n; y != 1; y = e[p[y] ^ 1].to) Flow = min(Flow, e[p[y]].cap);
    int dist = 0;
    for (int y = n; y != 1; y = e[p[y] ^ 1].to) dist += e[p[y]].cost;
    if (dist <= k) {
      if (dist) Flow = 1;
      for (int y = n; y != 1; y = e[p[y] ^ 1].to) {
        e[p[y]].cap -= Flow;
        e[p[y] ^ 1].cap += Flow;
      }
      k -= Flow * dist;
      res += Flow;
    } else
      k = -1;
  }
  return res;
}
int main() {
  cin >> n >> k;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      cin >> a[i][j];
      if (a[i][j]) {
        addEdge(i, j, a[i][j], 0);
        addEdge(i, j, INF, 1);
      }
    }
  }
  cout << flow() << endl;
  return 0;
}
