#include <bits/stdc++.h>
using namespace std;
const int64_t MOD = 1e9 + 7;
const int64_t N = 1e6 + 5;
struct edge {
  int64_t to, flow, cap, cost, rev;
};
struct MinCostMaxFlow {
  int64_t nodes;
  vector<int64_t> prio, curflow, prevedge, prevnode, q, pot;
  vector<bool> inqueue;
  vector<vector<edge> > graph;
  MinCostMaxFlow() {}
  MinCostMaxFlow(int64_t n)
      : nodes(n),
        prio(n, 0),
        curflow(n, 0),
        prevedge(n, 0),
        prevnode(n, 0),
        q(n, 0),
        pot(n, 0),
        inqueue(n, 0),
        graph(n) {}
  void addEdge(int64_t source, int64_t to, int64_t capacity, int64_t cost) {
    edge a = {to, 0, capacity, cost, (int64_t)graph[to].size()};
    edge b = {source, 0, 0, -cost, (int64_t)graph[source].size()};
    graph[source].push_back(a);
    graph[to].push_back(b);
  }
  void bellman_ford(int64_t source, vector<int64_t> &dist) {
    fill(dist.begin(), dist.end(), INT_MAX);
    dist[source] = 0;
    int64_t qt = 0;
    q[qt++] = source;
    for (int64_t qh = 0; (qh - qt) % nodes != 0; qh++) {
      int64_t u = q[qh % nodes];
      inqueue[u] = false;
      for (auto &e : graph[u]) {
        if (e.flow >= e.cap) continue;
        int64_t v = e.to;
        int64_t newDist = dist[u] + e.cost;
        if (dist[v] > newDist) {
          dist[v] = newDist;
          if (!inqueue[v]) {
            inqueue[v] = true;
            q[qt++ % nodes] = v;
          }
        }
      }
    }
  }
  pair<int64_t, int64_t> minCostFlow(int64_t source, int64_t dest,
                                     int64_t maxflow) {
    bellman_ford(source, pot);
    int64_t flow = 0;
    int64_t flow_cost = 0;
    while (flow < maxflow) {
      priority_queue<pair<int64_t, int64_t>, vector<pair<int64_t, int64_t> >,
                     greater<pair<int64_t, int64_t> > >
          q;
      q.push({0, source});
      fill(prio.begin(), prio.end(), INT_MAX);
      prio[source] = 0;
      curflow[source] = INT_MAX;
      while (!q.empty()) {
        int64_t d = q.top().first;
        int64_t u = q.top().second;
        q.pop();
        if (d != prio[u]) continue;
        for (int64_t i = 0; i < graph[u].size(); i++) {
          edge &e = graph[u][i];
          int64_t v = e.to;
          if (e.flow >= e.cap) continue;
          int64_t newPrio = prio[u] + e.cost + pot[u] - pot[v];
          if (prio[v] > newPrio) {
            prio[v] = newPrio;
            q.push({newPrio, v});
            prevnode[v] = u;
            prevedge[v] = i;
            curflow[v] = min(curflow[u], e.cap - e.flow);
          }
        }
      }
      if (prio[dest] == INT_MAX) break;
      for (int64_t i = 0; i < nodes; i++) pot[i] += prio[i];
      int64_t df = min(curflow[dest], maxflow - flow);
      flow += df;
      for (int64_t v = dest; v != source; v = prevnode[v]) {
        edge &e = graph[prevnode[v]][prevedge[v]];
        e.flow += df;
        graph[v][e.rev].flow -= df;
        flow_cost += df * e.cost;
      }
    }
    return {flow, flow_cost};
  }
};
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int64_t n, k;
  cin >> n >> k;
  int64_t arr[n][n];
  for (int64_t i = 0; i < n; i++) {
    for (int64_t j = 0; j < n; j++) {
      cin >> arr[i][j];
    }
  }
  int64_t l = 0;
  int64_t r = 1000000000;
  int64_t ans = 0;
  while (l <= r) {
    int64_t mid = (l + r) / 2;
    MinCostMaxFlow mcf = MinCostMaxFlow(n);
    for (int64_t i = 0; i < n; i++) {
      for (int64_t j = 0; j < n; j++) {
        if (i != j) {
          mcf.addEdge(i, j, arr[i][j], 0);
          if (arr[i][j] > 0) mcf.addEdge(i, j, MOD, 1);
        }
      }
    }
    pair<int64_t, int64_t> res = mcf.minCostFlow(0, n - 1, mid);
    int64_t cost = res.second;
    int64_t flow = res.first;
    if (cost <= k && flow == mid) {
      ans = mid;
      l = mid + 1;
    } else {
      r = mid - 1;
    }
  }
  cout << ans;
  return 0;
}
