#include <bits/stdc++.h>
using namespace std;
const int maxn = 205, inf = 16843009, inf2 = 100000;
struct edge {
  int u, v, cap, cost;
  int next;
  edge() {}
  edge(int u, int v, int cap, int cost, int next)
      : u(u), v(v), cap(cap), cost(cost), next(next) {}
} Edge[100005];
int NE, head[maxn], dist[maxn], par[maxn], a[maxn][maxn];
bool vis[maxn];
inline void init() {
  NE = 0;
  memset(head, -1, sizeof(head));
}
inline void addEdge(int u, int v, int cap, int cost) {
  Edge[NE] = edge(u, v, cap, cost, head[u]);
  head[u] = NE++;
  Edge[NE] = edge(v, u, 0, -cost, head[v]);
  head[v] = NE++;
}
inline bool SPFA(int s, int t, int n) {
  int i, u, v;
  memset(vis, 0, sizeof(vis));
  memset(par, -1, sizeof(par));
  memset(dist, 1, sizeof(dist));
  vis[s] = true;
  dist[s] = 0;
  queue<int> q;
  q.push(s);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    vis[u] = false;
    for (i = head[u]; ~i; i = Edge[i].next) {
      v = Edge[i].v;
      int tmp = dist[u] + Edge[i].cost;
      if (Edge[i].cap && dist[v] > tmp) {
        dist[v] = tmp;
        par[v] = i;
        if (!vis[v]) {
          q.push(v);
          vis[v] = true;
        }
      }
    }
  }
  if (dist[t] == inf) return false;
  return true;
}
pair<int, int> MCMF(int s, int t, int n) {
  int flow = 0, i, minflow, mincost = 0;
  while (SPFA(s, t, n)) {
    minflow = inf;
    for (i = par[t]; ~i; i = par[Edge[i].u]) {
      minflow = min(minflow, Edge[i].cap);
    }
    flow += minflow;
    for (i = par[t]; ~i; i = par[Edge[i].u]) {
      Edge[i].cap -= minflow;
      Edge[i ^ 1].cap += minflow;
    }
    mincost += dist[t] * minflow;
  }
  return make_pair(flow, mincost);
}
pair<int, int> foo(int splitter, int n) {
  init();
  int source = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (a[i][j] != 0) {
        addEdge(i, j, a[i][j], 0);
        addEdge(i, j, inf2, 1);
      }
    }
  }
  addEdge(source, 1, splitter, 0);
  pair<int, int> flow = MCMF(0, n, n);
  return flow;
}
int main() {
  int n, k;
  scanf("%d %d", &n, &k);
  init();
  memset(a, 0, sizeof(a));
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      scanf("%d", &a[i][j]);
    }
  }
  int lo = 0, hi = 500000000, mid, res = 0;
  for (int j = 0; j < 100; j++) {
    mid = (lo + hi) / 2;
    pair<int, int> flow = foo(mid, n);
    if (flow.second <= k) {
      res = max(res, flow.first);
      lo = mid + 1;
    } else
      hi = mid;
  }
  cout << res << endl;
  return 0;
}
