#include <bits/stdc++.h>
using namespace std;
struct Edge {
  int to, from, capacity, cost;
};
const int N = 55;
vector<int> adj[N];
vector<Edge> edges;
const int INF = 1e9;
void add_edge(int u, int v, int capacity, int cost) {
  edges.push_back({v, u, capacity, cost});
  adj[u].push_back(edges.size() - 1);
  edges.push_back({u, v, 0, -cost});
  adj[v].push_back(edges.size() - 1);
}
void shortest_paths(int n, int v0, vector<int>& d, vector<int>& p) {
  d.assign(n, INF);
  d[v0] = 0;
  vector<bool> inq(n, false);
  queue<int> q;
  q.push(v0);
  p.assign(n, -1);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    inq[u] = false;
    for (int idx : adj[u]) {
      Edge e = edges[idx];
      int v = e.to;
      if (e.capacity > 0 && d[v] > d[u] + e.cost) {
        d[v] = d[u] + e.cost;
        p[v] = idx;
        if (!inq[v]) {
          inq[v] = true;
          q.push(v);
        }
      }
    }
  }
}
long long min_cost_flow(int N, int K, int s, int t) {
  int flow = 0;
  long long cost = 0;
  vector<int> d, p;
  while (flow < K) {
    shortest_paths(N, s, d, p);
    if (d[t] == INF) break;
    int f = K - flow;
    int cur = t;
    while (cur != s) {
      Edge e = edges[p[cur]];
      f = min(f, e.capacity);
      cur = e.from;
    }
    flow += f;
    cost += f * 1ll * d[t];
    cur = t;
    while (cur != s) {
      Edge& e1 = edges[p[cur]];
      Edge& e2 = edges[p[cur] ^ 1];
      e1.capacity -= f;
      e2.capacity += f;
      cur = e1.from;
    }
  }
  if (flow < K)
    return 1e18;
  else
    return cost;
}
int c[55][55];
int main() {
  int n, k;
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) scanf("%d", &c[i][j]);
  }
  int lo = 0, hi = 1e9, ans = 0;
  while (lo <= hi) {
    int mid = (lo + hi) / 2;
    edges.clear();
    for (int i = 1; i <= n; i++) adj[i].clear();
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        if (c[i][j] > 0) {
          add_edge(i, j, c[i][j], 0);
          add_edge(i, j, mid, 1);
        }
      }
    }
    long long cost = min_cost_flow(n + 1, mid, 1, n);
    if (cost <= k)
      ans = mid, lo = mid + 1;
    else
      hi = mid - 1;
  }
  printf("%d\n", ans);
}
